0229. Majority Element II
=========================
题目信息
--------
:题号: 0229
:难度: Medium
:主题: 数组、计数、Boyer-Moore 投票
:原题: `LeetCode 0229 `_
:重点: 出现次数严格大于 floor(n/3)、答案至多两个、去重、返回顺序不限
题目重述
--------
给定整数数组 ``nums``,返回所有出现次数严格大于 ``floor(n/3)`` 的不同元素,其中 ``n`` 是数组长度。阈值是“严格大于”,出现次数恰好等于 ``floor(n/3)`` 的元素不能加入答案。
数组长度位于 ``[1, 5 * 10^4]``,元素位于 ``[-10^9, 10^9]``。满足条件的不同元素最多有两个;结果中不能重复包含同一个值,多个答案的返回顺序不作要求。题目的进阶目标是在线性时间和常数额外空间内完成。
自建示例
--------
两个元素都超过阈值:
.. code-block:: text
输入:nums = [4, 2, 4, 3, 2, 4, 2, 5]
输出:[4, 2]
解释:n=8,floor(n/3)=2;4 和 2 都出现 3 次,严格大于 2。返回 [2, 4] 也同样合法。
恰好等于阈值不计入:
.. code-block:: text
输入:nums = [1, 1, 2, 2, 3, 4]
输出:[]
解释:floor(6/3)=2,1 和 2 都只出现 2 次,没有任何元素严格超过阈值。
为什么候选最多两个
------------------
若有三个不同元素都出现严格多于 ``n/3`` 次,它们的出现次数总和会严格大于 ``n``,
与数组总长度矛盾。因此只需保留两个可能的候选,而不能在第一遍扫描后直接相信它们的计数;
抵消过程只负责排除不可能者,最终仍需第二遍精确计数。
Boyer--Moore 两候选
------------------
维护 ``candidate1/count1`` 和 ``candidate2/count2``:
#. 当前值等于某个候选时增加对应计数;
#. 否则若某个计数为 0,就用当前值占据该候选位置;
#. 两个候选都不同且计数非零时,同时把两个计数减一。
最后一种操作等价于删除一组三个互不相同的元素。这种删除不会改变任何元素是否能超过 ``n/3`` 的结论,
因为每个真实多数元素即使被成组抵消,仍会在剩余序列中留下可能的候选。第一遍结束后只剩至多两个候选,
第二遍按 ``count > n/3`` 验证严格阈值。
正确性说明
----------
把每次“两候选都非零且遇到第三种值”的减计数看成同时删去一组不同值。任何出现次数超过 ``n/3`` 的元素,
不可能在所有抵消后完全消失:每次抵消至多消耗它一个出现,同时还要消耗两个其他元素;若它全部被消掉,
原数组中它的次数不会超过总数的三分之一。故所有合格元素都在两个候选中。
第二遍直接统计原数组中的真实次数,保留且仅保留严格大于 ``floor(n/3)`` 的候选,保证结果无误且不重复。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector majorityElement(std::vector& nums) {
int candidate1 = 0, candidate2 = 1;
int count1 = 0, count2 = 0;
for (int value : nums) {
if (value == candidate1) {
++count1;
} else if (value == candidate2) {
++count2;
} else if (count1 == 0) {
candidate1 = value;
count1 = 1;
} else if (count2 == 0) {
candidate2 = value;
count2 = 1;
} else {
--count1;
--count2;
}
}
count1 = 0;
count2 = 0;
for (int value : nums) {
if (value == candidate1) ++count1;
if (value == candidate2) ++count2;
}
std::vector answer;
const int threshold = static_cast(nums.size()) / 3;
if (count1 > threshold) answer.push_back(candidate1);
if (count2 > threshold && candidate2 != candidate1) {
answer.push_back(candidate2);
}
return answer;
}
};
代码分析
--------
两遍扫描均为 ``O(n)``,只保存两个候选及其计数,除返回数组外额外空间为 ``O(1)``。
第二遍不可省略:第一遍的计数是抵消后的相对余额,不是原数组出现次数。候选初始化为两个不同值,
且相等分支先于空计数分支,避免把同一候选重复占用;输入数组不被排序或修改。