169 Follow Up: 229. Majority Ele

给定 array of integers, 返回个数多余 len/3 的 items

要求： Linear Runtime, O(1) Space

思路：满足条件的 items 的可能个数是 0，1，2。仍然使用 Boyer-Moore Vote。每次选取三个不一样的 items，然后从 array 中删除，直到 array 中不存在三个不一样的 items。

public List<Integer> majorityElement(int[] nums) {
    List<Integer> res = new LinkedList<>();
    int item1 = 0, item2 = 0;
    int count1 = 0, count2 = 0;

    for (int num: nums) {
        if (item1 == num) {
            count1++;
        } else if (item2 == num) {
            count2++;
        } else if (count1 == 0) {
            count1 = 1;
            item1 = num;
        } else if (count2 == 0) {
            count2 = 1;
            item2 = num;
        } else {
            count1--;
            count2--;
        }
    }

    count1 = 0;
    count2 = 0;
    for (int num: nums) {
        if (item1 == num) {
            count1++;
        } else if (item2 == num) {
            count2++;
        }
    }
    if (count1 > nums.length / 3) res.add(item1);
    if (count2 > nums.length / 3) res.add(item2);

    return res;
}