Majority Element II

Description:

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

Similar to the solution of Majority Element I. However, in this question, keep two variable as the count for two majority elements. In the end, another round of scan of the array is required to check if the amount of the two elements satisfy the requirement.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
        if (nums.length == 0) return res;
        if (nums.length == 1) {res.add(nums[0]); return res;}
        int num1 = nums[0], num2 = nums[1], count1 = 0, count2 = 0;
        for(int i = 0; i < nums.length; i++) {
            if (nums[i] == num1) {
                count1 ++;
            } else if (nums[i] == num2) {
                count2 ++;
            } else if (count1 == 0) {
                num1 = nums[i];
                count1 = 1;
            } else if (count2 == 0) {
                num2 = nums[i];
                count2 = 1;
            } else {
                count1--; count2--;
            }
        }
        count1 = 0; count2 = 0;
        for(int n : nums) {
            if (n == num1) count1++;
            else if (n == num2) count2++;
        }
        if (count1 > nums.length/3) res.add(num1);
        if (count2 > nums.length/3) res.add(num2);
        return res;
    }
}