给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2

解法 1

暴力法，两层循环，第一层循环遍历每个元素 i，第二层循环计算每个元素的出现次数 count，当出现次数大于数组一半长度的元素就将其返回。这里的 // 代表地板除。

def majority_element(nums):
    majority_count = len(nums) // 2
    for num in nums:
        count = sum(1 for elem in nums if elem == num)
        if count > majority_count:
            return num

时间复杂度：
空间复杂度：O(1)

解法 2

哈希表，首先还是循环遍历每个元素，然后将元素的出现次数记录在哈希表中（字典），若某个元素在哈希表中的出现次数大于数组一半长度，就将其返回。

def majority_element(nums):
    majority_count = len(nums) // 2
    map = {}
    for i in nums:
        map[i] = map.get(i, 0) + 1
        if map.get(i) > majority_count:
            return i

执行用时 :228 ms
内存消耗 :15.2 MB

如果利用 Python collections 模块中的 Counter() 函数，代码将更加简洁，更令人惊喜的是，虽然 Counter 类也是基于继承的字典类 dict 实现的，但执行时间却缩短了不少。

import collections

def majority_element(nums):
    counts = collections.Counter(nums)
    return max(counts.keys(),key=counts.get)

执行用时 :188 ms
内存消耗 :15 MB

时间复杂度：O(n)，遍历 n 个元素复杂度为 O(n)，查询哈希表复杂度为 O(1)，所以最终时间复杂度为 O(n)。
空间复杂度：O(n)，因为哈希表需要存储最多 n / 2 个不同的元素。

解法 3

排序法，如果所有数字按照单调递增或者单调递减的顺序排序后，那么某个众数元素的下标一定为 （ 代表地板除），如下图所示：

def majority_element(nums):
    nums.sort()
    return nums[len(nums)//2]

执行用时 :208 ms
内存消耗 :15.1 MB

时间复杂度：O(n log n)，快排的时间复杂度为 O(n log n)。
空间复杂度：O(1)。

解法 4

随机法，由于超过半数的元素都是众数，可以尝试随机选取一个元素判断是否为众数。

def majority_element(nums):
    majority_count = len(nums) // 2
    while True:
        num = random.choice(nums)
        if sum(1 for elem in nums if elem == num) > majority_count:
            return num

执行用时 :212 ms
内存消耗 :15.1 MB

时间复杂度：理论上这个算法有可能跑无穷次（如果我们一直无法随机到众数），所以最坏时间复杂度是没有上限的。
空间复杂度：O(1)

解法 5

分治法，我们可以利用分治的思想，将一个任务拆成多个子任务，最后再将子任务的结果进行比较或合并，得到最终结果。我们将输入的数组不断拆成左右两段子数组，直到元素个数为 1，那么该元素即为子数组的众数，将该元素返回到上一层。来到上一层后，元素个数一定不为 1，那就需要比较左右两段子数组的众数，当左右两段子数组的众数相同时，将众数返回，继续作为上一层左段子数组的众数；当左右两段子数组的众数不同时，将左右两段子数组出现次数较多的众数返回，继续作为上一层左段子数组的众数。直到回溯到第一层，即可得到完整数组的众数。

def majority_element(nums):
    def majority_element_rec(low, high):
        # 当元素个数为1,该元素即为众数
        if low == high:
            return nums[low]
        # 将数组切为两段,分别递归计算每段的众数
        mid = (high - low) // 2 + low
        left = majority_element_rec(low, mid)
        right = majority_element_rec(mid + 1, high)
        # 当左右两段的众数相同,返回众数
        if left == right:
            return left
        # 当左右两段众数不同,分别计算两个众数出现次数
        left_count = sum(1 for i in range(low, high + 1) if nums[i] == left)
        right_count = sum(1 for i in range(low, high + 1) if nums[i] == right)
        # 若左段众数较大,则返回左段众数,否则返回右段众数
        return left if left_count > right_count else right
    return majority_element_rec(0, len(nums) - 1)

执行用时 :376 ms
内存消耗 :15.7 MB

时间复杂度：O(n log n)，递归不断地将任务一分为二，总共会分 log n 次，也就是 log n 个子任务，在每个子任务中，当左右两段子数组众数不同时，需要做两次长度为 n 的线性扫描，复杂度为 O(n)，所以最终时间复杂度是 O(n log n)。
空间复杂度：O(log n)，尽管分治算法没有直接分配额外的数组空间，但因为递归的过程，在栈中使用了一些非常数的额外空间。因为算法每次将数组从每一层的中间断开，所以数组长度变为 1 之前只有 O(log n) 次切断。由于递归树是平衡的，所以从根到每个叶子节点的长度都是 O(log n) 。由于递归树是深度优先的，空间复杂度等于最长的一条路径，也就是 O(log n)。

解法 6

摩尔投票法（Boyer-Moore），如果将数组的众数元素记为 +1，非众数元素记为 -1，那么，数组所有元素之和一定大于 0。通过循环遍历数组每个元素，将第一个元素视为众数，计数器 +1，如遇到非众数则计数器 -1，当计数器归零后再重新开始，遍历结束后，计数器保留的元素即为众数。

例如：[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]，竖线即为计数器归零的时刻，最后保留的众数为 7。

def majority_element(nums):
    num = None
    count = 0
    for i in nums:
        if count == 0:
            num = i
        count += 1 if i == num else -1
    return num

执行用时 :216 ms
内存消耗 :15.2 MB

时间复杂度：O(n)
空间复杂度：O(1)

参考

https://leetcode-cn.com/problems/majority-element/