/**
1. 找到数组中出现次数大于 1/3 的数, 可能有一个, 也可能有2个, 我们先假定有两个分别是 x,y 那么可以将集合分为 x, y, other 三类数
2. 如果将 x, y, other 一一对应, 那么x, y必将有剩余, 我们统计数组中3个不同的数, 使用2个坑, 对于每个数nums[i]:
    2.1 如果一个坑是空的, 且nums[i] 不在另一个坑内, count[index] ++;
    2.2 如果nums[i] 在两个坑的任一个, 那么count[index] ++;
    2.3 如果坑都有值, 且都与nums[i] 不相等, 说明找到一个互不相同的三元组, 那么count[0]--, count[1]--;

3. 最后2个坑内的值就是候选值, 重新验证一下, 出现次数 > n/3 的就是结果之一.
*/


class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length, len = n / 3;
        int[] slot = new int[2];
        int[] count = new int[2];

        for (int i = 0 ; i < n; i++){
            int x = nums[i];
            if (count[0] == 0 && (count[1] == 0 || slot[1] != x )) {
                slot[0] = x;
                count[0] ++;
            } else if (count[1] == 0 && (count[0] == 0 || slot[0] != x)){
                slot[1] = x;
                count[1] ++;
            } else if (slot[0] == x){
                count[0] ++;
            } else if (slot[1] == x){
                count[1] ++;
            } else {
                count[0] --;
                count[1] --;
            }
        }

        List<Integer> result = new ArrayList<>();
        count[0] = 0;
        count[1] = 0;
        for (int i = 0 ; i < n ; i ++){
            if (nums[i] == slot[0]) count[0] ++;
            else if (nums[i] == slot[1]) count[1] ++;
        }

        if (count[0] > len) result.add(slot[0]);
        if (count[1] > len) result.add(slot[1]);
        return result;
    }
}