Majority Element

169. 多数元素

分析

使用摩尔投票法（Boyer-Moore Voting Algorithm），通过维护一个候选元素和计数器，在一次遍历中找到多数元素

将候选元素初始化为空，计数器设为 0
遍历数组：
- 如果计数器为 0，则更新候选元素为当前元素，计数器设为 1
- 如果当前元素等于候选元素，计数器加 1
- 如果当前元素不等于候选元素，计数器减 1
遍历结束后，候选元素即为多数元素

这是因为多数元素的出现次数大于其他元素出现次数的总和，因此在消耗所有计数后，多数元素一定会留下

时间复杂度

只需一次遍历数组，时间复杂度为 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
public:
    int majorityElement(vector<int>& nums)
    {
        int res = 0, cnt = 0; // 初始化候选元素和计数器
        for (int num : nums)
        {
            if (cnt == 0)       // 如果计数器为 0，更新候选元素
                res = num, cnt = 1;
            else if (res == num) // 当前元素等于候选元素，计数器加 1
                ++cnt;
            else                // 当前元素不等于候选元素，计数器减 1
                --cnt;
        }
        return res; // 返回多数元素
    }
};