题目
给定一个大小为 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