LC 229. 求众数 II
题目描述
这是 LeetCode 上的 229. 求众数 II ,难度为 中等。
给定一个大小为 n
的整数数组,找出其中所有出现超过 ⌊ n/3 ⌋
次的元素。
示例 1:
1 |
|
示例 2:
1 |
|
示例 3:
1 |
|
提示:
- $1 <= nums.length <= 5 * 10^4$
- $-10^9 <= nums[i] <= 10^9$
进阶:尝试设计时间复杂度为 $O(n)$、空间复杂度为 $O(1)$ 的算法解决此问题。
哈希表计数
一个朴素的做法是使用「哈希表」进行计数,在计数完成后将所有出现次数超过 $n / 3$ 的元素加入答案。
代码:
1 |
|
- 时间复杂度:$O(n)$
- 空间复杂度:$O(n)$
摩尔投票
在前置 🧀 简单题学投票算法 中,我们使用「摩尔投票」在 $O(1)$ 空间复杂度内找到了出现次数超过一半的元素,即出现次数大于 $n / 2$ 的数。
对于本题,我们需要统计出现次数超过 $n / 3$ 的数。
我们可以不失一般性的将其拓展为「统计出现次数超过 $n / k$ 的数」。
可以证明,出现次数超过 $n / k$ 的数最多只有 $k - 1$ 个。否则必然违背「数总共只有 $n$ 个」或者「当前统计的是出现次数超过 $n / k$ 的数」的前提条件。
当明确了符合要求的数的数量之后,我们可以使用有限变量来代表这 $k - 1$ 个候选数及其出现次数。
然后使用「摩尔投票」的标准做法,在建立数组时同时 check
这 $k - 1$ 个数,假设当前遍历到的元素为 $x$:
- 如果 $x$ 本身是候选者的话,则对其出现次数加一;
- 如果 $x$ 本身不是候选者,检查是否有候选者的出现次数为 $0$:
- 若有,则让 $x$ 代替其成为候选者,并记录出现次数为 $1$;
- 若无,则让所有候选者的出现次数减一。
当处理完整个数组后,这 $k - 1$ 个数可能会被填满,但不一定都是符合出现次数超过 $n / k$ 要求的。
需要进行二次遍历,来确定候选者是否符合要求,将符合要求的数加到答案。
上述做法正确性的关键是:若存在出现次数超过 $n / k$ 的数,最后必然会成为这 $k - 1$ 个候选者之一。
我们可以通过「反证法」来进行证明:若出现次数超过 $n / k$ 的数 $x$ 最终没有成为候选者。
有两种可能会导致这个结果:
数值 $x$ 从来没成为过候选者:
如果 $x$ 从来没成为过候选者,那么在遍历 $x$ 的过程中,必然有 $k - 1$ 个候选者被减了超过 $n / k$ 次,假设当前 $x$ 出现次数为 $C$,已知 $C > n / k$,此时总个数为
再根据 $C > n / k$,可知 $C * k > n$,而我们总共就只有 $n$ 个数,因此该情况恒不成立。
数值 $x$ 成为过候选者,但被逐出替换了:
同理,被逐出替换,说明发生了对 $x$ 出现次数减一的动作(减到 $0$),每次的减一操作,意味着有其余的 $k - 2$ 个候选者的出现次数也发生了减一动作,加上本身被遍历到的当前数 $num[i]$,共有 $k - 1$ 个数字的和 $x$ 被一同统计。
因此,根据我们摩尔投票的处理过程,如果 $x$ 成为过候选者,并被逐出替换,那么同样能够推导出我们存在超过 $n$ 个数。
综上,如果存在出现次数超过 $n / k$ 的数,其必然会成为 $k - 1$ 个候选者之一。
代码:
1 |
|
- 时间复杂度:$O(n)$
- 空间复杂度:$O(1)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.229
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!