308，求衆數 II

給定一個大小為 n 的數組，找出其中所有出現超過 ⌊ n/3 ⌋ 次的元素。

說明: 要求算法的時間複雜度為 O(n)，空間複雜度為 O(1)。

示例 1:

輸入: [3,2,3]
輸出: [3]      

示例 2:

輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]      

1public List<Integer> majorityElement(int[] nums) {
 2    List<Integer> res = new ArrayList<>();
 3    if (nums.length == 0)
 4        return res;
 5    int num1 = nums[0];
 6    int num2 = nums[0];
 7    int count1 = 1;
 8    int count2 = 0;
 9
10    for (int val : nums) {
11        if (val == num1)
12            count1++;
13        else if (val == num2)
14            count2++;
15        else if (count1 == 0) {
16            num1 = val;
17            count1++;
18        } else if (count2 == 0) {
19            num2 = val;
20            count2++;
21        } else {
22            count1--;
23            count2--;
24        }
25    }
26    count1 = 0;
27    count2 = 0;
28    for (int val : nums) {
29        if (val == num1)
30            count1++;
31        else if (val == num2)
32            count2++;
33    }
34    if (count1 > nums.length / 3)
35        res.add(num1);
36    if (count2 > nums.length / 3)
37        res.add(num2);
38    return res;
39}