550 字
3 分钟
leetcode 169

Leetcode 169 多数元素#

给定一个大小为 n 的数组 nums,返回其中的多数元素。 多数元素是指在数组中出现次数大于 𝑛2 的元素。 你可以假设数组是非空的,并且给定的数组总是存在多数元素。 要求实现一个时间复杂度 𝑂(𝑛),空间复杂度 𝑂(1) 的算法。

示例 1:

输入:nums = [3,2,3]
输出:3

示例 2:

输入:nums = [2,2,1,1,1,2,2]
输出:2

暴力#

题干意思就是找到众数,暴力的方法就是开个 HashTable 统计一下所有数的出现次数, 然后再遍历拿出现次数最多的数,但是这个方法显然是不符合复杂度要求的。

Boyer-Moore#

这里记录一下看到有意思的题解吧,Boyer-Moore 投票算法。

假设把目标的数定义为 +1,非目标定义为 -1,那么所有数的和一定是正的, 因为超过半数都是 +1,基于这个原理,我们定义一个 cnt: int = 0, 那么此时就该想如何得到目标。遍历数组的过程中,我们维护一个动态改变的 winner, 每遇到一个数和当前的 winner 一致,那么 cnt+1,否则出现了不一样的数, 此时我们就需要判断了,假设 cnt 已经为 0 了,那么产生了新的 winner, 如果 cnt != 0,那么还没产生新 winner,让 cnt-1

class Solution {
public:
int majorityElement(vector<int>& nums) {
int winner = nums[0];
int cnt{1};
for (int i = 1; i < nums.size(); ++i) {
if (nums[i] == winner) {
++cnt;
} else {
if (cnt == 0) {
winner = nums[i];
++cnt;
} else {
--cnt;
}
}
}
return winner;
}
};

其实简单来说,就是我们知道最多的数一定会成为最终的 winner,不断争抢得到 cnt, 也就是 nums[i] == winner 的发生次数是最多的,由于我们的目标出现次数大于 𝑛2, 因此我们可以把其中的部分数与其他数抵消让 cnt=0,剩下的数则会让 cnt 一直自增。

也就是100个数中有51个114514,49个其他数,可以拿出49个114514与49个其他的数抵消,剩下两个114514一定会成为 winner

leetcode 169
https://laplace825.github.io/posts/leetcode/majorityelement/
作者
Laplace
发布于
2025-08-09
许可协议
CC BY-NC-SA 4.0