LeetCode刷题 NO.169 多数元素 (简单)

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

示例

输入：nums = [2,2,1,1,1,2,2]
输出：2

解析

1）这道题的解法很多，但第一次见不一定能做出来，所以算法题无他，见多识广而已；

2）本文中主要介绍三种解法，排序法、投票法、统计法，都比较巧妙。

代码示例

1、投票法

因为多数元素是出现次数大于 [n/2] 的元素，所以数组排序后，[n//2] 号元素一定是答案。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        nums.sort()
        return nums[len(nums)//2]

执行用时：28 ms, 在所有 Python3 提交中击败了 99.74% 的用户.

2、投票法

遍历数组，依次和待选元素比较，如果相同则次数加1，不同则减1，多数元素存在绝对数量优势，遍历完后剩下的就是答案。这也是半数以上算通过的选举方法。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num = None
        count = 0
        for i in nums:
            if count == 0:
                num = i
            count += 1 if i==num else -1
        return num

执行用时：40 ms, 在所有 Python3 提交中击败了 84.67% 的用户.

3、统计法

前面两种解法，都可以在时间 O(n) 和空间 O(1) 的复杂度上求解，但有一个重要的前提，就是元素个数要超过 [n/2]，这是一个很强的条件。

实际场景中，更多的可能是找到出现次数最多的即可，不一定数量上会超过 [n/2]，所以统计每个值出现的次数，取最大泛化能力更好。

from collections import Counter

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = Counter(nums)
        return max(counts, key=counts.get)

执行用时：32 ms, 在所有 Python3 提交中击败了 98.42% 的用户.