Majority Element II

Source

• leetcode: 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.

Hint:

How many majority elements could it possibly have?
Do you have a better hint? Suggest it!

Java

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();

        int n1=0;
        int n2=0;
        int candidate1=0;
        int candidate2=0;

        for(int num: nums){
            if(num==candidate1){
                n1++;
            }
            else if(num==candidate2){
                n2++;
            }
            else if(n1==0){
                candidate1=num;
                n1=1;
            }
            else if(n2==0){
                candidate2=num;
                n2=1;
            }
            else{
                n1--;
                n2--;
            }
        }

        n1=0;
        n2=0;

        for (int num : nums){
            if (num == candidate1) {
                ++n1;
            } else if (num == candidate2) {
                ++n2;
            }
        }

        if (n1 > nums.length / 3) {
            res.add(candidate1);
        }
        if (n2 > nums.length / 3) {
            res.add(candidate2);
        }

        return res;        

    }
}