229. Majority Element II2

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]29. Majority Element II

---

本题要求一个数组中出现次数大于 ⌊ n/3 ⌋的所有数字，上一题LeetCode Majority Element是求数组中出现次数大于 ⌊ n/2 ⌋的数字，而且保证数组中有且仅有一个这样的众数。 在本题中，并不一定存在符合题意的众数存在，如果存在，最多有2个这样的众数，可以用反证法，如果有3个这样的众数，那么每个元素的出现次数最多是n/3，不可能超过。 思路还可以用上一题的摩尔投票法，即我们假设最多存在两个这样的众数，且随便设置这两个不同的众数为0和1，然后用摩尔投票法过一遍数组，看看最终记录的众数是哪两个。 最后再过一遍数组，统计一下这两个数的次数是否超过n/3。 完整代码如下：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums)
    {
        int num1 = 0, num2 = 1, cnt1 = 0, cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1) { // (1)
                cnt1++;
            }
            else if (nums[i] == num2) { // (2)
                cnt2++;
            }
            else if (cnt1 == 0) { // (3)
                num1 = nums[i];
                cnt1++;
            }
            else if (cnt2 == 0) { // (4)
                num2 = nums[i];
                cnt2++;
            }
            else {
                cnt1–;
                cnt2–;
            }
        }
        vector<int> ans;
        cnt1 = 0;
        cnt2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == num1)
                cnt1++;
            else if (nums[i] == num2)
                cnt2++;
        }
        if (cnt1 > nums.size() / 3)
            ans.push_back(num1);
        if (cnt2 > nums.size() / 3)
            ans.push_back(num2);
        return ans;
    }
};

注意代码中的(1)(2)判断必须在(3)(4)判断前面，因为如果遇到[8,8,7,7,7]这样的样例，如果(3)(4)在前面的话，num1和num2就都会被赋值为8，导致丢掉了8这个结果。还有我们一开始必须给num1和num2随便设置不同的两个数。
本代码提交AC，用时16MS。