public static List<Integer> majorityElement(int[] nums) {
if(nums.length==0)
return new LinkedList<>();
List<Integer> ls = new LinkedList<>();
int num1=nums[0],num2=nums[0],cnt1=0,cnt2=0;
for(int i=0,len=nums.length;i<len;i++){
if(nums[i]==num1)
cnt1++;
else if(nums[i]==num2){
cnt2++;
}
else if(cnt1==0){
num1=nums[i];
cnt1=1;
}
else if(cnt2==0){
num2 = nums[i];
cnt2=1;
}
else {
cnt1--;
cnt2--;
}
}
cnt1=0;
cnt2=0;
for(int i=0,len=nums.length;i<len;i++){
if(nums[i]==num1)
cnt1++;
else if(nums[i]==num2){
cnt2++;
}
}
if(cnt1>nums.length/3)
ls.add(num1);
if(cnt2>nums.length/3)
ls.add(num2);
System.out.println(cnt1+" "+num1);
System.out.println(cnt2+" "+num2);
return ls;
}
首先砰苍，一個數(shù)組中出現(xiàn)次數(shù)大于n／3的數(shù)字最多只可能有兩個潦匈，所以建立兩個候選數(shù)字。
再遍歷數(shù)組赚导，若和其中一個候選數(shù)字相同茬缩，則計數(shù)+1，否則-1吼旧。
