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;
}
首先，一个数组中出现次数大于n／3的数字最多只可能有两个，所以建立两个候选数字。
再遍历数组，若和其中一个候选数字相同，则计数+1，否则-1。
