Python3数组中出现次数超过一半的数字（散列表/Counter/摩尔投票法）

数组中出现次数超过一半的数字

• 题目
• 解题思路
• code1:使用dict
• code2：使用Counter
• 扩展:摩尔投票法

题目

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

解题思路

最好想的思路是使用散列表进行存储每个数字出现的次数，由此可以使用dict或者使用collections.Counter进行计数。

code1:使用dict

class Solution: def majorityElement(self, nums: List[int]) -> int: #使用dict记录每个元素的个数 cnt = {} for item in nums: if item not in cnt: cnt[item] = 1 else: cnt[item] += 1 halfLen = len(nums)//2 for item in cnt: if cnt[item]>halfLen: return item 

code2：使用Counter

class Solution: from collections import Counter def majorityElement(self, nums: List[int]) -> int: #使用Counter记录每个元素的个数 cnt = Counter(nums) half_len = len(nums)//2 for item in cnt: if cnt[item]>half_len: return item 

扩展:摩尔投票法

上面使用散列表的方式，时间/空间复杂度都为$O(N)$，而摩尔投票法可以将空间复杂度降为$O(1)$.
摩尔投票法简单理解为正负相消法，我们有一个序列，序列中有个数字num的个数超过一半，这就说明num能与其他数字相互抵消并在最后只剩下num。
由此我们可以得到相应的代码为：

class Solution: def majorityElement(self, nums: List[int]) -> int: vote = 0 major = nums[0]#初始化`num` for item in nums: if item == major: vote += 1 else: vote -= 1 if vote < 0: major,vote = item, 1 return major 

本文地址：https://blog.csdn.net/Giotto_Ven/article/details/108246873