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.

Have you met this question in a real interview? 

Yes

Example

Given [1, 2, 1, 2, 1, 3, 3], return 1.

Note

There is only one majority number in the array.

Challenge

O(n) time and O(1) extra space.

public class Solution {
    /**
     * @param nums: A list of integers
     * @return: The majority number that occurs more than 1/3
     */
    public int majorityNumber(ArrayList<Integer> nums) {
        // write your code
       
        int a = 0, b = 0, ca = 0, cb = 0;
        boolean isA = false, isB = false;
        for(int i = 0; i < nums.size(); i++){
            if(!isA || nums.get(i) == a){
                ca++;
                a = nums.get(i);
                isA = true;
            } else if(!isB || nums.get(i) == b){
                cb++;
                b = nums.get(i);
                isB = true;
            } else{
                ca--;
                cb--;
                if(ca == 0)
                isA = false;
                if(cb == 0)
                isB = false;
            }
        }
        if(!isA) return b;
        if(!isB) return a;
        int c = 0;
        for(int num : nums){
            if(num == a) c++;
        }
        return c > nums.size()/3 ? a : b;
    }
}