[Leetcode]229. Majority Element II

Question

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.

Solution

For finding the majority elements, there is a very famous algorithm Boyer–Moore majority vote algorithm. But the original algorithm is for finding the majority number that appears more than ⌊ n/2 ⌋ times. So we need to modify the algorithm to find numbers that appears more than n/3. Use 2 counter to keep tracking of 2 candidate numbers.

For every number in array,

1. Check if it is one of the two candidate numbers.
2. Check if its’ counter is 0, if counter is 0, update candidate number and set counter to 1.
3. If it is not satisfy either of the above conditions. Decrement the counter by 1.

After the first round loop, we have two “majority” numbers but we don’t know if they appears more than n/3 time. So we start another loop to count the occurrence time.

Finally, if the occurrence time is more than n/3, add it to result set.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> ret  = new LinkedList<Integer>();
        if( nums.length == 0 ){
            return ret;
        }
        int count1 = 0;
        int count2 = 0;
        int m1 = 0;
        int m2 = 0;
        for( int n : nums ){
            if( n == m1 ){
                count1++;
            }else if( n == m2 ){
                count2++;
            }else if ( count1 == 0 ){
                m1 = n;
                count1 = 1;
            }else if ( count2 == 0 ){
                m2 = n;
                count2 = 1;
            }else{
                count1--;
                count2--;
            }
        }
        
        count1 = 0;
        count2 = 0;
        
        for(int n : nums ){
            if( n == m1 ){
                count1++;
            }else if( n == m2 ){
                count2++;
            }
        }
        
        if( count1 > nums.length/3 ) ret.add(m1);
        if( count2 > nums.length/3 ) ret.add(m2);
        
        return ret;
        
    }
}