题目描述

给定一个大小为 n 的数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例

示例 1：

输入: [3,2,3]
输出: [3]

示例2：

输入: [1,1,1,3,3,2,2,2]
输出: [1,2]

解答方法

方法一：多数投票法

思路

超过n/3的数最多只能有两个。先选出两个候选人A,B。 遍历数组，分三种情况：

1.如果投A（当前元素等于A），则A的票数++;

2.如果投B（当前元素等于B），B的票数++；

3.如果A,B都不投（即当前与A，B都不相等）,那么检查此时A或B的票数是否减为0：
3.1 如果为0,则当前元素成为新的候选人；
3.2 如果A,B两个人的票数都不为0，那么A,B两个候选人的票数均减一；
遍历结束后选出了两个候选人，但是这两个候选人是否满足>n/3，还需要再遍历一遍数组，找出两个候选人的具体票数。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        candidate1 = None
        candidate2 = None
        cnt1, cnt2 = 0, 0
        for num in nums:
            if num == candidate1:
                cnt1 +=1
            elif num == candidate2:
                cnt2 += 1
            elif cnt1 == 0:
                candidate1 = num
                cnt1 +=1
            elif cnt2 == 0:
                candidate2 = num
                cnt2 += 1
            else:
                cnt1 -= 1
                cnt2 -= 1
        return [n for n in (candidate1,candidate2) if nums.count(n) > len(nums) // 3] 

时间复杂度

O(n)

空间复杂度

O(1)

方法二：哈希表

思路

就是逐个计数，再遍历寻找计数值 > n/3的数。

代码

class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        dic = {}
        for num in nums:
            if num in dic:
                dic[num] +=1
            else:
                dic[num] = 1
        res = []
        for i in dic:
            if dic[i] > len(nums) // 3:
                res.append(i)
        return res

时间复杂度

O(n)

空间复杂度

O(n)