LeetCode 169 多数元素

1. 题目

概括一下题意：找出数组中的众数

思路一：哈希查表

自己唯一能想到的方法，遍历数组的同时构建哈希表，边遍历边查找。时间复杂度$O(n)$，空间复杂度$O(n)$

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        num_dict = {}
        thre = len(nums)/2
        for idx, num in enumerate(nums):
            if num in num_dict:
                num_dict[num] += 1
            else:
                num_dict[num] = 1
            if num_dict[num] > thre:
                return num

思路二；排序取中间

对数组进行排序，数组中间的元素一定是众数

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

时间复杂度$O(n \log n)$，空间复杂度$O(1)$

思路三：摩尔投票法

记众数的票数为+1，非众数的票数为−1，则：

1. 所有元素的总票数一定大于0
2. 若数组前a个元素的票数为0，则后n-a的元素的总票数一定大于0，且后n-a的元素的众数就是全局的众数

有了上面2个推论，可以构造查找众数的思路：

1. 遍历数组，当票数为0时，假设下一个数为众数
2. 若当前元素==众数，则票数+1；若当前元素!=众数，则票数-1。
3. 如此循环，直到遍历结束，返回最后假设的众数。

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

时间复杂度$O(n)$，空间复杂度$O(1)$