上海外贸网站建设,怎么创网址,对电子商务网站建设与维护的总结,资源下载WordPress主题本文属于「征服LeetCode」系列文章之一#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁#xff0c;本系列将至少持续到刷完所有无锁题之日为止#xff1b;由于LeetCode还在不断地创建新题#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章… 本文属于「征服LeetCode」系列文章之一这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁本系列将至少持续到刷完所有无锁题之日为止由于LeetCode还在不断地创建新题本系列的终止日期可能是永远。在这一系列刷题文章中我不仅会讲解多种解题思路及其优化还会用多种编程语言实现题解涉及到通用解法时更将归纳总结出相应的算法模板。 为了方便在PC上运行调试、分享代码文件我还建立了相关的仓库https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解还可以一同分享给他人。 由于本系列文章的内容随时可能发生更新变动欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。 数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组找出其中的主要元素。若没有返回 -1 。请设计时间复杂度为 O(N) 、空间复杂度为 O(1) 的解决方案。
示例 1
输入[1,2,5,9,5,9,5,5,5]
输出5示例 2
输入[3,2]
输出-1示例 3
输入[2,2,1,1,1,2,2]
输出2题目集合
169. 多数元素面试题 17.10. Find Majority Element LCCI229. 多数元素 II Check If a Number Is Majority Element in a Sorted Array 1157. 子数组中占绝大多数的元素困难
解法 Boyer-Moore 投票算法
由于题目要求时间复杂度 O ( n ) O(n) O(n) 和空间复杂度 O ( 1 ) O(1) O(1) 因此符合要求的解法只有 Boyer-Moore 投票算法。这一投票算法在求出现次数大于 ⌊ n / 2 ⌋ \lfloor n / 2 \rfloor ⌊n/2⌋ 的元素 x x x 时很好理解如果我们把 x x x 记为 1 1 1 把其他数记为 − 1 -1 −1 将它们全部加起来显然和大于 0 0 0 从结果本身我们可以看出 x x x 比其他数多。
我们首先给出 Boyer-Moore 算法的详细步骤
维护一个候选主要元素 c a n d i d a t e candidate candidate 和候选主要元素的出现次数 c o u n t count count 初始时 c a n d i d a t e candidate candidate 为任意值 c o u n t 0 count0 count0 遍历数组 nums \textit{nums} nums 中的所有元素遍历到元素 x x x 时在判断 x x x 之前如果 c o u n t 0 count0 count0 我们先将 x x x 的值赋给 c a n d i d a t e candidate candidate 否则不更新 c a n d i d a t e candidate candidate 的值。随后我们判断 x x x 如果 x c a n d i d a t e xcandidate xcandidate 则将 c o u n t count count 加 1 1 1 如果 x ≠ c a n d i d a t e x\ne candidate xcandidate 则将 c o u n t count count 减 1 1 1 。 遍历结束之后如果数组 n u m s nums nums 中存在主要元素则 c a n d i d a t e candidate candidate 即为主要元素否则 c a n d i d a t e candidate candidate 可能为数组中的任意一个元素。由于不一定存在主要元素因此需要第二次遍历数组验证 c a n d i d a t e candidate candidate 是否为主要元素。第二次遍历时统计 c a n d i d a t e candidate candidate 在数组中的出现次数如果出现次数大于数组长度的一半则 c a n d i d a t e candidate candidate 是主要元素返回 c a n d i d a t e candidate candidate 否则数组中不存在主要元素返回 − 1 -1 −1 。
举一个具体的例子例如下面的这个数组
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]在遍历到数组中的第一个元素以及每个在 | 之后的元素时 c a n d i d a t e candidate candidate 都会因为 c o u n t count count 的值变为 0 0 0 而发生改变。最后一次 c a n d i d a t e candidate candidate 的值从 5 5 5 变为 7 7 7 也就是这个数组中的主要元素。
Boyer-Moore 算法的正确性较难证明这里给出一种较为详细的用例子辅助证明的思路供参考 1.首先根据算法步骤中对 c o u n t count count 的定义可以发现在对整个数组进行遍历的过程中 c o u n t count count 的值一定非负。这是因为如果 c o u n t count count 的值为 0 0 0 那么在这一轮遍历的开始时刻我们会将 x x x 的值赋予 c a n d i d a t e candidate candidate 并在接下来的一步中将 c o u n t count count 的值增加 1 1 1 。因此 c o u n t count count 的值在遍历过程中一直保持非负。
2.那么 c o u n t count count 本身除了计数器之外还有什么更深层次的意义呢我们还是以数组
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]作为例子首先写下它在每一步遍历时 c a n d i d a t e candidate candidate 和 c o u n t count count 的值
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
candidate: 7 7 7 7 7 7 5 5 5 5 5 5 7 7 7 7
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4我们再定义一个变量 v a l u e value value 它和真正的主要元素 m a j maj maj 绑定。在每一步遍历时如果当前的数 x x x 和 m a j maj maj 相等那么 v a l u e value value 的值加 1 1 1 否则减 1 1 1 。 v a l u e value value 的实际意义即为到当前的这一步遍历为止主要元素出现的次数比非主要元素多出了多少次。我们将 v a l u e value value 的值也写在下方
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4有没有发现什么我们将 c o u n t count count 和 v a l u e value value 放在一起
nums: [7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]
count: 1 2 1 2 1 0 1 0 1 2 1 0 1 2 3 4
value: 1 2 1 2 1 0 -1 0 -1 -2 -1 0 1 2 3 4发现在每一步遍历中 c o u n t count count 和 v a l u e value value 要么相等要么互为相反数并且在候选主要元素 c a n d i d a t e candidate candidate 就是 m a j maj maj 时它们相等 c a n d i d a t e candidate candidate 是其它的数时它们互为相反数
为什么会有这么奇妙的性质呢这并不难证明我们将候选主要元素 c a n d i d a t e candidate candidate 保持不变的连续的遍历称为「一段」。在同一段中 c o u n t count count 的值是根据 c a n d i d a t e x candidate x candidatex 的判断进行加减的。那么如果 c a n d i d a t e candidate candidate 恰好为 m a j maj maj 那么在这一段中 c o u n t count count 和 v a l u e value value 的变化是同步的如果 c a n d i d a t e candidate candidate 不为 m a j maj maj 那么在这一段中 c o u n t count count 和 v a l u e value value 的变化是相反的。因此就有了这样一个奇妙的性质。
这样以来由于
我们证明了 c o u n t count count 的值一直为非负在最后一步遍历结束后也是如此由于 v a l u e value value 的值与真正的主要元素 m a j maj maj 绑定并且它表示「主要元素出现的次数比非主要元素多出了多少次」那么在最后一步遍历结束后 v a l u e value value 的值为正数在最后一步遍历结束后 c o u n t count count 非负 v a l u e value value 为正数所以它们不可能互为相反数只可能相等即 c o u n t v a l u e count value countvalue 。因此在最后「一段」中 c o u n t count count 的 v a l u e value value 的变化是同步的也就是说 c a n d i d a t e candidate candidate 中存储的候选主要元素就是真正的主要元素 m a j maj maj 。
class Solution {
public:int majorityElement(vectorint nums) {int candidate 0, count 0;for (int num : nums) {if (count 0) candidate num;if (candidate num) count;else --count;}count 0;for (int num : nums) if (num candidate) count;return count * 2 nums.size() ? candidate : -1;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n) 其中 n n n 是数组 n u m s nums nums 的长度。空间复杂度 O ( 1 ) O(1) O(1) 。只需要常数的额外空间。
