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.
Code
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> rst = new ArrayList<Integer>();
if (nums==null || nums.length==0) return rst;
int count1=0, count2=0, candidate1 = -1, candidate2 = -1;
for (int num:nums){
if(num==candidate1) count1++;
else if (num==candidate2) count2++;
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 num:nums){
if (num==candidate1) count1+=2;
else count1--;
if (num==candidate2) count2+=2;
else count2--;
}
if (count1>0) rst.add(candidate1);
if (count2>0) rst.add(candidate2);
return rst;
}
}
Reference