229. 求众数 II

image-20211022094507477

解题思路：

  • 遍历计数法
    • 先遍历vector，用unordered_map记录下每个数出现的次数
    • 逐个判断出现次数是否>nums.size()/3，符合则加入ans中
    • 时间复杂度为O(n),空间复杂度为O(n)
  • 摩尔投票法
    • 根据出现超过⌊ n/3 ⌋次的元素可以得出最多可能有2个这样的元素
    • 让互不相同的三个元素互相抵消，最终会得到两个可能符合的元素
    • 遍历计数，判断两个元素是否符合，符合则将其加入到ans中
    • 时间复杂度为O(n),空间复杂度为O(1)

以下为C++代码：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        //MARKER:摩尔投票法
        int vote1=0;
        int vote2=0;
        int num1=0;
        int num2=0;

        //求出可能的两个num
        for(auto num:nums){
            if(vote1>0 && num1==num){
                vote1++;
            }else if (vote2>0 && num2==num){
                vote2++;
            }else if (vote1==0){
                num1=num;
                vote1=1;
            }else if (vote2==0){
                num2=num;
                vote2=1;
            }else{
                vote1--;
                vote2--;
            }
        }

        int count1=0;
        int count2=0;
        for(auto num:nums){
            if(num==num1) count1++;
            else if(num==num2) count2++;
        }
        vector<int> ans;
        if (count1>nums.size()/3){
            ans.push_back(num1);
        }
        if (count2>nums.size()/3){
            ans.push_back(num2);
        }

        return ans;
    }
};