Majority Element II

Question

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

Note: The algorithm should run in linear time and in O(1) space.

Example:
Input: [3,2,3]
Output: [3]

LeetCodeleetcode.com/problems/majority-element-ii

Solution

/*
最多2个出现次数超过n/3的元素
算法：类似于Majority Element I, 用两个count， 如果重复则++， 反之--；
*/
public List<Integer> majorityElement(int[] nums) {
    List<Integer> result = new ArrayList<>();
    if (nums.length == 0) {
        return result;
    }
    
    int count1 = 0, count2 = 0;
    int num1 = 0, num2 = 0;
    
    for (int i = 0; i < nums.length; i++) {
        int n = nums[i];
        if (count1 == 0 && num2 != n) {
            num1 = n;
            count1++;
        }else if (num1 == n) {
            count1++;
        }else if (count2 == 0) {
            num2 = n;
            count2++;
        }else if (num2 == n) {
            count2++;
        }else {
            count1--;
            count2--;
        }            
    }
    
    //最后得到num1,num2不一定是正解，再循环验证一遍
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] == num1) {
            count1++;
        }
        if (nums[i] == num2) {
            count2++;
        }
    }
    if (count1 > nums.length/3) {
        result.add(num1);
    }
    if (count2 > nums.length/3 && num1 != num2) {
        result.add(num2);
    }
    return result;
}