0169. Majority Element
======================
题目信息
--------
:题号: 0169. 多数元素
:难度: Easy
:主题: 数组、计数、排序、Boyer–Moore 投票
:原题: `LeetCode 0169 `_
:重点: 利用严格过半保证,将不同元素成对抵消并把完整频次表压缩成候选与余额
题目重述
--------
给定长度为 ``n`` 的整数数组 ``nums``,返回其中的多数元素。多数元素的出现次数严格大于
``floor(n / 2)``,题目保证它一定存在。
进阶目标是用 ``O(n)`` 时间和 ``O(1)`` 额外空间完成。
自建示例
--------
.. code-block:: text
输入:nums = [2,2,1,1,1,2,2]
输出:2
2 出现 4 次,严格超过长度 7 的一半;扫描中的临时候选可以变化,最终仍回到 2。
.. code-block:: text
输入:nums = [-5,3,-5,-5,3]
输出:-5
多数性的定义只依赖频次,与数值大小和正负无关。
.. code-block:: text
输入:nums = [7]
输出:7
唯一元素出现 1 次,严格大于 floor(1 / 2) = 0。
C++ 实现
--------
.. code-block:: cpp
#include
#include
#include
class Solution {
private:
int repeatedCounting(const std::vector& nums) {
for (int candidate : nums) {
int occurrences = 0;
for (int value : nums) {
if (value == candidate) {
++occurrences;
}
}
if (occurrences > static_cast(nums.size()) / 2) {
return candidate;
}
}
return nums.front();
}
int frequencyTable(const std::vector& nums) {
std::unordered_map occurrences;
occurrences.reserve(nums.size());
int threshold = static_cast(nums.size()) / 2;
for (int value : nums) {
if (++occurrences[value] > threshold) {
return value;
}
}
return nums.front();
}
int sortedMiddle(std::vector nums) {
std::sort(nums.begin(), nums.end());
return nums[nums.size() / 2];
}
int cancellationCandidate(const std::vector& nums) {
int candidate = 0;
int balance = 0;
for (int value : nums) {
if (balance == 0) {
candidate = value;
}
if (value == candidate) {
++balance;
} else {
--balance;
}
}
return candidate;
}
public:
int majorityElement(std::vector& nums) {
return cancellationCandidate(nums);
}
};
题解
----
从定义出发的重复计数
~~~~~~~~~~~~~~~~~~~~
按定义,可以把每个位置的值都当作候选,再扫描整个数组统计其出现次数。
``repeatedCounting`` 一定会找到题目保证存在的多数元素,但相同候选会被反复统计,最坏
时间为 ``O(n²)``。瓶颈不在“判断是否相等”,而在没有保存此前已经得到的频次。
``frequencyTable`` 用哈希表把每个值的计数保留下来。每读一个元素只增量更新一次;计数
首次超过 ``floor(n/2)`` 时可以立即返回,因为后续元素不会让该计数下降。这将期望时间
降为 ``O(n)``,代价是最多保存 ``O(n)`` 个不同值。
排序暴露了另一种结构
~~~~~~~~~~~~~~~~~~~~
如果数组排好序,多数元素会形成长度超过 ``n/2`` 的连续块。这样长的块无论从哪里开始,
都必然覆盖下标 ``n/2``,所以中间位置就是答案。``sortedMiddle`` 不再维护全部频次,
但复制和排序需要 ``O(n)`` 空间与 ``O(n log n)`` 时间;若原地排序可以省去复制空间,
却会修改输入。
题目的“严格超过一半”还能提供更强的信息:多数元素的数量大于其余所有元素数量之和。
这允许不排序、不记频次,只不断删除互不相同的元素对。
成对抵消为何保持多数性
~~~~~~~~~~~~~~~~~~~~~~~~
假设当前总长度为 ``N``,真正多数元素出现 ``M`` 次,满足 ``M > N/2``。删除两个不同
元素时:
* 若其中一个是多数元素,新的计数和长度是 ``M-1``、``N-2``,而
``M-1 > (N-2)/2`` 与原不等式等价;
* 若两者都不是多数元素,多数计数不变、总长度减少 2,多数性只会更强。
因此任意反复删除不同值对,都不会改变“剩余元素中的多数是谁”。真正多数元素不可能在
抵消完成后彻底消失;否则其余元素也至少要提供同样多的配对数量,与严格过半矛盾。
候选与余额压缩了哪些历史
~~~~~~~~~~~~~~~~~~~~~~~~
``cancellationCandidate`` 不真的删除数组元素。``candidate`` 表示当前未配对元素的值,
``balance`` 表示该值尚未抵消的数量:
* 当前值等于候选,无法与已有候选配成不同值对,余额加一;
* 当前值不同,拿它与一个未配对候选抵消,余额减一;
* 余额为零时,之前这个抵消段没有留下任何元素,当前值可以开启新的候选段。
完整哈希表中的每个频次被压缩成了两个标量。``balance`` 不是候选在整个前缀中的真实
出现次数,而是当前抵消段中的净剩余票数;把它误解为总频次会无法解释候选为何能改变。
具体走读
~~~~~~~~
对 ``[2,2,1,1,1,2,2]``:
.. code-block:: text
读入值 动作 candidate balance
2 余额为 0,选择 2;同值加票 2 1
2 同值加票 2 2
1 异值抵消 2 1
1 异值抵消 2 0
1 余额为 0,选择 1;同值加票 1 1
2 异值抵消 1 0
2 余额为 0,选择 2;同值加票 2 1
中途候选 2 的余额归零并不表示 2 已被证明不是多数,只表示已处理的那一段可以整体成对
删除。最后未被抵消的候选是 2;由题目保证存在多数元素,它必然就是真正多数。
存在性保证的重要性
~~~~~~~~~~~~~~~~~~
Boyer–Moore 第一遍只产生“抵消后的候选”。若题目不保证多数元素存在,例如
``[1,2,3]``,算法仍会返回某个候选,却不能证明它超过一半;此时必须再扫描一次验证
候选频次。本题已经明确保证存在,因此第二遍验证不会改变结果,可以省略。
方案选择与复杂度
~~~~~~~~~~~~~~~~
重复计数时间 ``O(n²)``、空间 ``O(1)``;哈希计数期望时间 ``O(n)``、空间 ``O(n)``;
排序取中点时间 ``O(n log n)``,当前实现因复制数组使用 ``O(n)`` 空间。Boyer–Moore
只扫描一次,时间 ``O(n)``、额外空间 ``O(1)``,同时满足进阶目标,因此主解采用
``cancellationCandidate``。