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.

Hint:

How many majority elements could it possibly have?

Thinking:

This question is similar with Majority Element which can be solved by Boyer–Moore majority vote algorithm.

Solution:

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new ArrayList<Integer>();
    int count1 = 0, count2 = 0, can1 = 0, can2 = 1;

    for (int num: nums){
        if (num == can1)
            count1++;
        else if (num == can2)
            count2++;
        else if (count1 == 0){
            can1 = num;
            count1 = 1;
        }
        else if (count2 == 0){
            can2 = num;
            count2 = 1;
        }
        else{
            count1--;
            count2--;
        }
    }
    count1 = 0;
    count2 = 0;
    for (int num: nums){
        if (num == can1)
            count1++;
        else if (num == can2)
            count2++;
    }

    if (count1 > nums.length / 3)
        res.add(can1);
    if (count2 > nums.length / 3 && can1 != can2)
        res.add(can2);

    return res;
}