思路
摩尔投票法(要求必定存在大于n/2的元素):初始cnt = 0,往后走如果遇到相等的cnt++,不一样cnt–
如果cnt为0 的话,那么更换res为当前的nums
来自力扣评论区有趣的解释
核心就是对拼消耗。
玩一个诸侯争霸的游戏,假设你方人口超过总人口一半以上,并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。
那就大混战呗,最差所有人都联合起来对付你(对应你每次选择作为计数器的数都是众数),或者其他国家也会相互攻击(会选择其他数作为计数器的数),但是只要你们不要内斗,最后肯定你赢。
最后能剩下的必定是自己人。
时间复杂度$O(n)$ 空间复杂度$O(1)$
代码
class Solution {
public:
int majorityElement(vector<int>& nums) {
int res = 0 ,cnt = 0;
for(auto it : nums){
if(cnt == 0){
cnt++ ;
res = it;
}
else {
res == it ? cnt ++ : cnt --;
}
}
return res;
}
};