题目

解法：投票算法

思路

Boyer-Moore 投票算法，通过抵消不同的元素来找到多数元素。

该算法的正确性基于抵消思想：将多数元素记为 +1，其他元素记为 -1，总和必然大于 0。遍历数组时，维护当前候选元素及其计数。当计数归零时，说明之前的元素中候选元素与其他元素数量相等，相互抵消。由于多数元素总数超过一半，它最终一定会成为最后的候选元素。

• Step 1: 初始化计数器 cot 为 0
• Step 2: 遍历数组中的每个元素 i
• Step 3: 如果 cot 为 0，将当前元素 i 设为候选元素 now，cot 设为 1
• Step 4: 否则，如果 i 等于 now，cot 加 1；否则 cot 减 1
• Step 5: 返回最终的候选元素 now

复杂度

• 时间复杂度: $O(n)$，只需一次线性遍历数组。
• 空间复杂度: $O(1)$，仅使用常数级别的额外变量。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int now ;
        int cot = 0;
        for(auto i:nums){
            if(cot == 0){
                now = i;
                cot = 1;
            }
            else{
                cot += i==now?1:-1;
            }
        }
        return now;
    }
};