因为是超过 n / 2的,所以必然是绝大多数,那么让可以用x记录当前记录的数,c记录当前记录的数的库存,通过这样的方式逐步去消化,最后的x即是绝大多数
证明:
反证法:如果最后x存储的不是题目所要求的数,那么意味着这个数都被抵消掉了,但是这个数是绝大多数,是绝不可能完全抵消掉的,从而得证做法正确
class Solution {
public int majorityElement(int[] nums) {
int x = 0, c = 0;
for(int i = 0; i < nums.length; i ++) {
if(c == 0) {
x = nums[i];
c ++;
}else if(nums[i] == x) c ++;
else c --;
}
return x;
}
}