题目描述

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

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

样例

输入：[1,1,1,3,3,2,2,2]
输出：[1,2]
说明：在输入数组中1,2分别出现了3次，超过了数组大小的1/3，因此输出1,2.

算法1

(摩尔投票算法) $O(n)$

由于题目限制了时间复杂度和空间复杂度，因此无法通过排序或哈希算法来解决，在这里采用摩尔投票算法。
摩尔投票算法(Boyer–Moore majority vote algorithm)又名多数投票算法，通过线性时间和常数空间来查找数组中的多数元素，关于该算法的详细理解和解释参考理解摩尔投票算法。我们只需要对原数组进行两趟扫描，第一趟扫描我们得到候选元素candidate，第二趟扫描我们判断candidate出现的次数是否大于⌊ n/3 ⌋。

在第一趟扫描时，当有候选元素未设置时，先将当前遍历到的元素设置为候选元素。若遍历到的元素和其中一个候选元素相等时，候选元素的计数器加一，若和两个候选元素都不相等，则两个候选元素的计数器都减一。通过第一趟扫描过后判断是否存在候选元素的计数器大于零，若存在，我们再进行第二趟扫描，判断候选元素出现次数是否满足题目要求（大于⌊ n/3 ⌋）。

时间复杂度分析：两轮扫描，时间复杂度为O(n)，空间复杂度为常数。

C++ 代码

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int numsSize = nums.size();
        vector<int>ret;
        if(numsSize == 0) return ret;
        int count1 = 0;
        int count2 = 0;
        int candidate1 = 0;
        int candidate2 = 0;
        for(auto i : nums)
        {//第一轮扫描确定candidate
            if(candidate1 == i) count1++;
            else if (candidate2 == i) count2++;
            else if (count1 == 0)
            {
                candidate1 = i;
                count1 = 1;
            }
            else if (count2 == 0)
            {
                candidate2 = i;
                count2 = 1;
            }
            else
            {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for(auto i : nums)
        {//第二轮扫描确定candidate是否符合要求
            if(candidate1 == i) count1++;
            else if(candidate2 == i) count2++;
        }
        if(count1 > numsSize/3) ret.push_back(candidate1);
        if(count2 > numsSize/3) ret.push_back(candidate2);
        return ret;
    }
};