題目
給定一個(gè)整型數(shù)組卿泽，找到主元素漱贱，它在數(shù)組中的出現(xiàn)次數(shù)嚴(yán)格大于數(shù)組元素個(gè)數(shù)的三分之一榄审。
** 注意事項(xiàng)**
數(shù)組中只有唯一的主元素
樣例
給出數(shù)組[1,2,1,2,1,3,3] 返回 1
分析
三三抵銷(xiāo)法驳概，但是也有需要注意的地方：
我們對(duì)cnt1,cnt2減數(shù)時(shí)，相當(dāng)于丟棄了3個(gè)數(shù)字（當(dāng)前數(shù)字旅薄，candidate1, candidate2）辅髓。也就是說(shuō)，每一次丟棄數(shù)字少梁，我們是丟棄3個(gè)不同的數(shù)字洛口。
而Majority number超過(guò)了1/3所以它最后一定會(huì)留下來(lái)。
而m > N/3, N - 3x > 0.
3m > N, N > 3x 所以 3m > 3x, m > x 也就是說(shuō) m一定沒(méi)有被扔完
最壞的情況凯沪，Majority number每次都被扔掉了绍弟，但它一定會(huì)在n1,n2中。
代碼
public class Solution {
/**
* @param nums: A list of integers
* @return: The majority number that occurs more than 1/3
*/
public int majorityNumber(ArrayList<Integer> nums) {
// write your code
int candidate1 = 0, candidate2 = 0;
int count1, count2;
count1 = count2 = 0;
for(int i=0;i<nums.size();i++) {
if(candidate1 == nums.get(i)) {
count1++;
} else if(candidate2 == nums.get(i)) {
count2++;
}else if(count1 == 0) {
candidate1 = nums.get(i);
count1 = 1;
}else if(count2 == 0) {
candidate2 = nums.get(i);
count2=1;
} else {
count1--;
count2--;
}
}
count1 = count2 = 0;
for(int i=0;i<nums.size();i++) {
if(nums.get(i) == candidate1) {
count1++;
} else if(nums.get(i) == candidate2) {
count2++;
}
}
return count1>count2?candidate1 :candidate2;
}
}
