229.majority-element-ii.md

给定一个大小为  n  的数组，找出其中所有出现超过  ⌊ n/3 ⌋  次的元素。

说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1)。

示例 1:

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

---

摩尔投票法

超过 n/3 次的候选人，可能有两个

我们要保留两个候选人位置，记录候选人和未被抵消掉的选票，选出得票最高的两人

然后，遍历计数，统计这 两人 得票是否超过 1/3

代码实现

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int p1 = 0, cnt1 = 0;
        int p2 = 0, cnt2 = 0;

        for (auto &n: nums){
            if (n == p1) {
                cnt1++;
                continue;
            }
            if (n == p2){
                cnt2++;
                continue;
            }
            if (cnt1 == 0){
                p1 = n;
                cnt1++;
                continue;
            }
            if (cnt2 == 0){
                p2 = n;
                cnt2++;
                continue;
            }
            cnt1--;
            cnt2--;
        }

        cnt1 = 0;
        cnt2 = 0;
        for (auto &n: nums){
            if (n ==p1) cnt1++;
            else if (n==p2) cnt2++;
        }
        vector<int> ans;
        if (cnt1> nums.size() /3) ans.push_back(p1);
        if (cnt2 > nums.size() /3) ans.push_back(p2);
        return ans;
    }
};