229、Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example 1:

Input: [3,2,3]
Output: [3]

Example 2:

Input: [1,1,1,3,3,2,2,2]
Output: [1,2]

思路

这里限定了时间和空间复杂度

首先，找到出现次数超过1/3的数，那么这个数最多有两个

其次，采用ＢＭ投票算法（Boyer-Moore Majority Vote algorithm）

• 设置一个数的计数器，在遍历数组的时候，如果是这个数，则计算器加一，不是则减一，用来计数超过一半的数非常方便。
• 在这里我们需要进行改进一下，设置两个计数器，来统计两个数出现的次数。

最后，判断这两个数出现次数是否超过1/3，即可。

c++11

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int f = 0, s = 0, cf = 0, cs = 0; // f = first, s = second, c = cnt
        // 得到最多的前两个数f和s
        for (int num : nums) {
            if (num == f) cf++;
            else if (num == s) cs++;
            else if (cf == 0) f = num, cf++;
            else if (cs == 0) s = num, cs++;
            else cf--, cs--;
        }
        // 计算最多前两个数的个数
        cf = 0, cs = 0;
        for (int num : nums) {
            if (num == f) cf++;
            else if (num == s) cs++;
        }
        // 判断这两个数的个数是否大于总长度的1/3，是则返回
        vector<int> res;
        int len = nums.size();
        if (cf > len/3) res.emplace_back(f);
        if (cs > len/3) res.emplace_back(s);
        return res;
    }
};

ac结果：

Runtime: 16 ms, faster than 86.30% of C++ online submissions for Majority Element II.
Memory Usage: 10.7 MB, less than 25.89% of C++ online submissions for Majority Element II.