多数元素
给定一个大小为 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)
