Leetcode 229. 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.

题意：从数组里找出所有出现次数大于n/3的数字，要求线性时间复杂度，O(1)的空间复杂度。

思路：

1. 通过遍历用哈希表统计的话很容易解决，但是空间复杂度无法满足要求。

2. 查看discuss，解法是Boyer-Moore Majority Vote algorithm。
   这个解法的核心是用两个变量表示当前的最佳候选值和当前候选值的票数（出现次数），之后把候选值的次数清零，重新遍历统计出候选值的实际出现次数，最后比较求出的候选值次数是否大于n/3.

public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length == 0) {
            return res;
        }

        int e1 = 0, e2 = 0;
        int c1 = 0, c2 = 0;
        for (int num : nums) {
            if (num == e1) {
                c1++;
            } else if (num == e2) {
                c2++;
            } else if (c1 == 0) {
                e1 = num;
                c1++;
            } else if (c2 == 0) {
                e2 = num;
                c2++;
            } else {
                c1--;
                c2--;
            }
        }

        c1 = 0;
        c2 = 0;
        for (int num : nums) {
            if (num == e1) {
                c1++;
            } else if (num == e2) {
                c2++;
            }
        }

        int len = nums.length;
        if (c1 > len / 3) {
            res.add(e1);
        }
        if (c2 > len / 3) {
            res.add(e2);
        }

        return res;
    }