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.

Find it.

Note

There is only one majority number in the array

Example

For [1, 2, 1, 2, 1, 3, 3] return 1

Challenge

O(n) time and O(1) space

 class Solution {
public:
    /**
     * @param nums: A list of integers
     * @return: The majority number occurs more than 1/3.
     */
    int majorityNumber(vector<int> nums) {
        int a, b;
        int count1 = 0, count2 = 0;
        
        for(int i = 0; i < nums.size(); i++) {
            if (count1 == 0 || a == nums[i]) {
              a = nums[i];
              count1++;
            }
            else if (count2 == 0 || b == nums[i]) {
                b = nums[i];
                count2++;
            }
            else {
                count1--;
                count2--;
                if (count1 == 0) {
                    a = nums[i];
                    count1 = 1;
                }
                else if(count2 == 0) {
                    b = nums[i];
                    count2 = 1;
                }
            }
        }
        
        // check if which one is the true majority
        count1 = 0, count2 = 0;
        for(int i : nums) {
            if (i ==a) count1++;
            if (i == b) count2++;
        }
        
        return count1 > count2? a : b;
    }
    
};