求众数2

发表于 分类于 阅读次数：

求众数2（难度：中等）

1

方法一：

在Python中，先用set()找出所有出现的元素，再使用count()判断出现次数大于n/3的。

1
2
3
4
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        set1 = set(nums)
        return [s for s in set1 if nums.count(s) > len(nums)//3]
2

然而时间复杂度不为O(n)。

方法二：Boyer-Moore 投票算法

超过n/3的数最多只能有两个。先选出两个候选人A,B（都令为nums[0]）。 遍历数组：

  1. 若当前元素等于A，则A的票数++;

  2. 若当前元素等于B，则B的票数++；

  3. 若当前元素与A，B都不相等，那么检查此时A或B的票数是否减为0：

    • 若为0，则当前元素成为新的候选人；

    • 若A、B票数均不为0，则A、B两个候选人的票数均减一；

遍历结束后选出了两个候选人，但是这两个候选人是否满足>n//3，还需要再遍历一遍数组，找出两个候选人的具体票数。

复杂度

时间复杂度：O(n)

空间复杂度：O(1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def majorityElement(self, nums: List[int]) -> List[int]:
        if(len(nums)==0):
            return []
        count1 = 0
        count2 = 0
        candidate1 = nums[0]
        candidate2 = nums[0]
 
        for num in nums:
            if num == candidate1:
                count1 += 1
            elif num == candidate2:
                count2 += 1
            else:
                if count1 == 0:
                    candidate1 = num
                    count1 += 1
                elif count2 == 0:
                    candidate2 = num
                    count2 += 1
                else:
                    count1 -= 1;
                    count2 -= 1;
    
        return set([num for num in [candidate1, candidate2] if nums.count(num) > len(nums)//3]) #加set的原因是避免返回两个相同的数
3