本文共 2034 字，大约阅读时间需要 6 分钟。

【思路1】排序，取中间元素

时间复杂度为O(nlogn)

class Solution:    def majorityElement(self, nums: List[int]) -> int:        if not nums:            return None        nums.sort()        return nums[int(len(nums)/2)]'''作者：xiao-xue-66链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/pythonti-jie-kuai-pai-zi-dian-di-xiao-by-xiao-xue-/来源：力扣（LeetCode）'''

【思路2】摩尔投票法

核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N)和 O(1) 。

推论： 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 > 0

class Solution:    def majorityElement(self, nums: List[int]) -> int:        votes = 0        for num in nums:            if votes == 0: x = num            votes += 1 if num == x else -1        return x'''作者：jyd链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/来源：力扣（LeetCode）'''

【扩展】由于题目说明 给定的数组总是存在多数元素 ，因此本题不用考虑 数组不存在众数 的情况。若考虑，需要加入一个 “验证环节” ，遍历数组 nums 统计 x 的数量。

• 若 x 的数量超过数组长度一半，则返回 x ；
• 否则，返回未找到众数；

时间和空间复杂度不变，仍为 O(N)和 O(1)。

class Solution:    def majorityElement(self, nums: List[int]) -> int:        votes, count = 0, 0        for num in nums:            if votes == 0: x = num            votes += 1 if num == x else -1        # 验证 x 是否为众数        for num in nums:            if num == x: count += 1        return x if count > len(nums) // 2 else 0 # 当无众数时返回 0'''作者：jyd链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/mian-shi-ti-39-shu-zu-zhong-chu-xian-ci-shu-chao-3/来源：力扣（LeetCode）'''

【思路3】哈希表

我们统计每个数字出现的次数，并保存在哈希表中。遍历哈希表，如果找到符合要求的数字，直接返回即可。

时间复杂度：O(N)。

class Solution:    def majorityElement(self, nums: List[int]) -> int:        dic = collections.Counter(nums)        for key,value in dic.items():            if value > len(nums) / 2:                return key'''作者：z1m链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/solution/ha-xi-biao-jie-fa-by-ml-zimingmeng/来源：力扣（LeetCode）'''

Counter（计数器）：用于追踪值的出现次数

转载地址：http://gyjii.baihongyu.com/