Majority Number II

题目：

Given an array of integers, the majority number is the number that occurs more than 1/3 of the size of the array.

分析：

超过1/3就意味着，如果只用一个candidate，那有可能被另外2/3的元素冲掉。所以这时候选用2个candidate，当其中一个为0的时候，只冲掉这个candidate，而另一个candidate的count不减少。所以其中一个candidate记录了majority number，而另一个candidate挡掉了1/3的元素，所以结果一定会至少保留一个majority number。

题目的关键就在于count2 == 0的时候，count1不减。

解法：

class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number occurs more than 1/3.
     */
    int majorityNumber(vector<int> nums) {
        // write your code here
        int res1 = INT_MIN;
        int res2 = INT_MIN;
        int count1 = 0;
        int count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (res1 == nums[i]) {
                count1++;
            } else if (res2 == nums[i]) {
                count2++;
            } else if (count1 == 0) {
                res1 = nums[i];
                count1++;
            } else if (count2 == 0) {
                res2 = nums[i];
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == res1) {
                count1++;
            }
            if (nums[i] == res2) {
                count2++;
            }
        }
        return count1 > count2 ? res1 : res2;
    }
};