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.
一刷
题解：类似于169. Majority Element。用两个count变量，和两个candidate
第一次iter:
如果nums[I] == candidate1, count1++;
如果nums[I] == candidate2, count2++;
如果count1 == 0, candidate1 = nums[I];
如果count2 == 0, candidate2 = nums[I];
else count1--, count2--;
第二次iter:
统计candidate1, candidate2出现次数，如果大于len/3，加入结果集中
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> res = new ArrayList<>();
if(nums == null || nums.length == 0) return res;
int count1 = 0, count2 = 0, candidate1 = 0, candidate2 = 0;
int len = nums.length;
for(int num : nums){
if(num == candidate1){
count1 += 1;
}
else if(num == candidate2){
count2 += 1;
}
else if(count1 == 0){
candidate1 = num;
count1 = 1;
}
else if(count2 == 0){
candidate2 = num;
count2 = 1;
}
else{
count1--;
count2--;
}
}
count1 = 0;
count2 = 0;
for(int i=0; i<nums.length; i++){
if(nums[i] == candidate1) count1++;
else if(nums[i] == candidate2) count2++;
}
if(count1>len/3) res.add(candidate1);
if(count2>len/3) res.add(candidate2);
return res;
}
}
