给定一个大小为 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}

解析：

最简单的一种方式是通过HashMap存储，key存储数组的值，value计算出现的次数，这种写法比较简单就不在列出，我们来看上面这种写法，超过1/3，说明最多也只有2个，我们先用两个变量num1和num2来存储。注意这里的关键点在第一个循环语句，也就是10到25行，其实也很好理解，我们还可以参照之前的146，求众数的第一种解法，这里就不在详细介绍。