Majority Element II

题目来源
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.
要求求出数组中出现次数超过n/3的元素，原来想着直接哈希，但是需要O(1)空间，感觉有点熟悉，记得之前在宿舍说过类似的题目。线性时间并且O(1)空间！我猜应该用位操作？但是想不出来怎么操作。
看了答案，得用到一个经典算法，叫Boyer-Moore Majority Vote algorithm，多数投票算法，之前也学过的，算法也很简单，但是忘了…
就是设置一个候选人以及一个计数器，假如出现相同的就加1，不同的就减1，当减到0的时候就换一个候选人。
然后这道题就是稍微改一下，变成有两个候选人，其他的就都一样了，注意最后还要再判断一下两个候选人是否符合要求，因为可能一共就两个元素
代码如下：

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> res;
        int cad1 = 0, cad2 = 0, count1 = 0, count2 = 0;
        for (int i=0; i<n; i++) {
            if (nums[i] == cad1)
                count1++;
            else if (nums[i] == cad2)
                count2++;
            else {
                if (count1 == 0) {
                    cad1 = nums[i];
                    count1++;
                }
                else if (count2 == 0) {
                    cad2 = nums[i];
                    count2++;
                }
                else {
                    count1--;
                    count2--;
                }
            }
        }
        count1 = 0, count2 = 0;
        for (int i=0; i<n; i++) {
            if (nums[i] == cad1)
                count1++;
            else if (nums[i] == cad2)
                count2++;
        }
        if (count1 > n/3)
            res.push_back(cad1);
        if (count2 > n/3)
            res.push_back(cad2);
        return res;
    }
};