LeetCode 面试题 17.10. Find Majority Element LCCI【摩尔投票法】简单

数组中占比超过一半的元素称之为主要元素。给你一个整数数组，找出其中的主要元素。若没有，返回 -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 LCCI
229. 多数元素 II
1. 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 count=0 count=0 ；
遍历数组 nums \textit{nums} nums 中的所有元素，遍历到元素 x x x 时，在判断 x x x 之前，如果 c o u n t = 0 count=0 count=0 ，我们先将 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 ：
1. 如果 x = c a n d i d a t e x=candidate x=candidate ，则将 c o u n t count count 加 1 1 1 ；
2. 如果 x ≠ c a n d i d a t e x\ne candidate x=candidate ，则将 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 ，否则数组中不存在主要元素，返回 − 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 candidate==x 的判断进行加减的。那么如果 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 count==value 。因此在最后「一段」中， 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(vector<int>& 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) 。只需要常数的额外空间。

memcpy0

LeetCode 面试题 17.10. Find Majority Element LCCI【摩尔投票法】简单

解法 Boyer-Moore 投票算法