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

Hint:

How many majority elements could it possibly have?
Do you have a better hint? Suggest it!

参考Lintcode: Majority Number II, 那道题只需找一个，这个要找出所有，其实最多就两个

观察可知，数组中至多可能会有2个出现次数超过 ⌊ n/3 ⌋ 的众数

记变量candidate1, candidate2为候选众数； count1, count2为它们对应的出现次数

遍历数组，记当前数字为num

若num与candidate1或candidate2相同，则将其对应的出现次数加1

否则，若count1或count2为0，则将其置为1，对应的候选众数置为num

否则，将count1与count2分别减1

最后，再统计一次候选众数在数组中出现的次数，若满足要求，则返回之。

最后这个再一次统计很关键，如果众数有两个，则必然是candidate1和candidate2; 但若只有一个，candidate1 或 candidate 2, 则不一定是count多的那个，例子参1 1 1 1 2 3 2 3 4 4 4 这个 1就会被消耗过多，最后余下的反而比4少。

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