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?

Code

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> result = new ArrayList<>();
        if (nums == null || nums.length == 0) return result;
        if (nums.length == 1) {
            result.add(nums[0]);
            return result;
        }
        
        int n1 = nums[0], n2 = 0, c1 = 1, c2 = 0;
        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];
            if (n == n1) {
                c1++;
            } else if (n == n2) {
                c2++;
            } else if (c1 == 0) {
                n1 = n;
                c1++;
            } else if (c2 == 0) {
                n2 = n;
                c2++;
            } else {
                c1--;
                c2--;
            }
        }
        
        c1 = 0;
        c2 = 0;
        
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == n1) c1++;
            else if (nums[i] == n2) c2++;
        }
        if (c1 > nums.length / 3) result.add(n1);
        if (c2 > nums.length / 3) result.add(n2);
        
        return result;
    }
}

Solution

摩尔投票法。
数组中至多可能会有2个出现次数超过 ⌊ n/3 ⌋ 的众数
记变量n1, n2为候选众数； c1, c2为它们对应的出现次数
遍历数组，记当前数字为num
若num与n1或n2相同，则将其对应的出现次数加1
否则，若c1或c2为0，则将其置为1，对应的候选众数置为num
否则，将c1与c2分别减1
最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。