多数元素
Majority Element
数组中有一个元素出现次数严格超过一半，找出这个多数元素。
在力扣中练习题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
提示：
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109- 输入保证数组中一定有一个多数元素。
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
解题思路
摩尔投票 · 两两抵消
不同的元素互相抵消，超过一半的那个一定留到最后
先想哈希计数：统计每个数出现多少次，时间 O(n)、空间 O(n)。排序也可以：多数元素超过一半，排序后一定落在中点，但时间是 O(n log n)。
摩尔投票利用一个更强的事实：把不同的两个元素删掉，多数元素仍然是多数元素。因为每次抵消最多删掉一个多数元素和一个其他元素，它的数量仍然超过剩余元素的一半。
算法只维护两个量：候选 candidate 和票数 count。
- count == 0 时，当前数接管候选；
- 与候选相同，count +1；
- 与候选不同，count -1。
自拟主例 [5,1,2,2,5,5,5] 中，第一个 5 和 1 抵消后 count 归零；两个 2 让候选变成 2，随后 5 把票数追平；最后一个 5 在 count 归零后重新接管，并以 1 票结束。
x = 2 与候选 2 相同，count +1 变为 1。
- x
- 2
- candidate
- 2
- count
- 1
x = 5 与候选 2 不同，计票归零；下一票会重新选候选。
- x
- 5
- candidate
- 2
- count
- 0
时间 O(n)，空间 O(1)。
易错点
- 先比较再判断 count == 0：空白状态下的旧候选会先被投一票。
- count 归零后不换候选：后续票数会记到已经失去支持的候选头上。
- 没有“多数元素一定存在”的前提时直接返回候选：需要第二遍验证它是否真的超过一半。
排序 · 取中点
多数元素超过一半，排序后必然覆盖中点
代码最短，时间 O(n log n)，还会修改输入数组；主解法摩尔投票是 O(n)、O(1)，更适合大数据。
如果某个元素出现次数严格大于 n/2，那么排序后它一定占据中点位置 n/2。
原因很直观：把相同的数排在一起，最长的连续段长度超过一半，不可能完全落在中点的左侧或右侧。所以直接返回 nums[n/2] 即可。
时间 O(n log n)，空间取决于排序实现（通常 O(log n) 递归栈）。它不依赖“多数元素一定存在”的额外验证，但如果题目不保证，仍然需要再数一遍。
- 1排序数组。
- 2返回 nums[n/2]。
易错点
- 下标取成 (n-1)/2：n 为偶数时中点有两个，取右边那个才是安全的 n/2。
- 直接修改输入数组：如果调用方还要用原顺序，需要先复制。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
nums = [5,1,2,2,5,5,5]先假设第一个数是候选，count 从 0 开始；count 为 0 时，下一个数会接管候选。
- candidate
- 5
- count
- 0
查看 C++ 代码
延伸阅读
- 摩尔投票可以扩展到“出现次数超过 n/k”的元素；维护 k-1 个候选，最后逐一验证。
- 如果没有“多数元素一定存在”的保证，必须第二遍扫描确认候选的出现次数。