抵消法
多数元素的数量比其他所有元素的总数还多。那么从前往后遍历，遇到相同元素，计数 + 1 +1 +1 ，遇到不同元素，计数 − 1 -1 −1 ，考虑边界，当旧数的出现次数减到 0 0 0 ，那么新数就可以替换旧数，并且计数 = 1 =1 =1 。
最终剩下的那个数，就是多数元素，并且它的计数 > 0 \gt 0 >0。
class Solution {
public:
int majorityElement(vector<int>& nums) {
int m=0,c=0;
for(auto &x:nums)
if(!c) m = x , c = 1;
else if(x==m) c++;
else c--;
return m;
}
};
- 时间复杂度 :O ( n ) O(n)O (n ) ，n n n 是数组长度， 一次遍历的时间复杂度O ( n ) O(n)O (n ) 。
- 空间复杂度 :O ( 1 ) O(1)O (1 ) ， 只使用常量级空间 。
AC
; 致语
- 理解思路很重要！
- 欢迎读者在评论区留言，墨染看到就会回复的。
Original: https://blog.csdn.net/Innocence02/article/details/128390588
Author: 清墨韵染
Title: 力扣(LeetCode)169. 多数元素(C++）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/778425/
转载文章受原作者版权保护。转载请注明原作者出处！