题目
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
来源：力扣(LeetCode)
Python解法
哈希表解法
这道题我想的是建立一个字典，字典的键为数组元素，对应的值是该元素在数组中出现的次数，然后遍历字典中的值，如果值大于数组长度的一半，则返回对应的键。
代码如下：
def majorityElement(self, nums: List[int]) -> int:
dict_count = {}
for i in nums:
dict_count[i] = dict_count.get(i, 0) + 1
n = len(nums)
for key, value in dict_count.items():
if value > n/2:
return key
排序解法
看到题解中一种超简单的解法：既然“多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素”，那我们对数组排序之后取中间的数，该数一定是我们要求的多数元素。
代码如下：
def majorityElement(self, nums: List[int]) -> int:
return sorted(nums)[len(nums) // 2]
摩斯投票法
题解中还提出了一种方法——摩尔投票法，也被称作「多数投票法」。算法解决的问题是：如何在任意多的候选人中(选票无序)，选出获得票数最多(必须超过得票数一半)的那个。
该算法可以分为两个阶段：①对抗阶段：分属两个候选人的票数进行两两对抗抵消；②计数阶段：计算对抗结果中最后留下的候选人票数是否有效。
根据上述的算法思想，我们遍历投票数组，将当前票数最多的候选人与其获得的(抵消后)票数分别存储在 major 与 count 中。
当我们遍历下一个选票时，判断当前 count 是否为零：
若 count == 0，代表当前 major 空缺，直接将当前候选人赋值给 major，并令 count++；
若 count != 0，代表当前 major 的票数未被完全抵消，因此令 count–，即使用当前候选人的票数抵消 major 的票数
代码如下：
def majorityElement(self, nums: List[int]) -> int:
major = 0
count = 0
for n in nums:
if count == 0:
major = n
if n == major:
count += 1
else:
count -= 1
return major