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少。
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<Integer>();
if (nums==null || nums.length==0) return res;
int count1=0, count2=0;
int candidate1=0, candidate2=0;
for (int i=0; i<nums.length; i++) {
if (count1 == 0) {
count1 = 1;
candidate1 = nums[i];
}
else if (count2 == 0 && candidate1 != nums[i]) {
count2 = 1;
candidate2 = nums[i];
}
else if (candidate1 == nums[i]) {
count1++;
}
else if (candidate2 == nums[i]) {
count2++;
}
else {
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for (int elem : nums) {
if (elem == candidate1) count1++;
else if (elem == candidate2) count2++;
}
if (count1>0 && count1 > nums.length/3) res.add(candidate1);
if (count2>0 && count2 > nums.length/3) res.add(candidate2);
return res;
}
}