CS 知识库

简体中文

English

简体中文

English

主题

Boyer-Moore 投票算法 ​

题目描述 ​

这是 LeetCode 169. 多数元素，难度为「简单」。

Tag : 「哈希表」、「摩尔投票」

数组中占比超过一半的元素称之为主要元素。给你一个 整数 数组，找出其中的主要元素。

若没有，返回 -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

提示：

  • n == nums.length
  • 1 <= n <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

哈希表 ​

一个朴素的做法是使用哈希表进行计数，如果发现某个元素数量超过总数一半，说明找到了答案。

c++代码：

c
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> counts;
        int majority = 0, cnt = 0;
        for (int num: nums) {
            ++counts[num];
            if (counts[num] > cnt) {
                majority = num;
                cnt = counts[num];
            }
        }
        return majority;
    }
};

Java代码：

java
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int x : nums) {
            map.put(x, map.getOrDefault(x, 0) + 1);
            if (map.get(x) > n / 2) return x;
        }
        return -1;
    }
}
  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(n)\)

摩尔投票 ​

这还是道「摩尔投票」模板题。

摩尔投票 ：在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；

需要注意的是，该算法在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果就可能是无效的随机元素。

换句话说，每次将两个不同的元素进行「抵消」，如果最后有元素剩余，则「可能」为元素个数大于总数一半的那个。

具体的，我们定义一个变量 来保存那个可能为主要元素的值，cnt用来记录该值的出现次数。然后在遍历数组nums 过程中执行如下逻辑：

  • 如果cnt为0 ：说明之前出现过的x已经被抵消完了，更新一下x为当前值，出现次数为 ：x = nums[i], cnt = 1；
  • 如果cnt不为0 ：说明之前统计的 还没被抵消完，这是根据nums[i]与x是否相等进行计算即可：cnt += nums[i] == x ? 1 : -1。

当处理完nums之后，我们得到了一个「可能」的主要元素。注意只是可能，因为我们在处理过程中只使用了x和cnt来记录，我们是无法确定最后剩下的x是经过多次抵消后剩余的主要元素，还是只是不存在主要元素的数组中的无效随机元素。

因此我们需要再进行一次遍历，检查这个「可能」的主要元素 的出现次数是否超过总数一半。

具体有兴趣的同学可以参考论文的证明过程，论文地址：MJRTYA Fast Majority Vote Algorithm

我们举一个具体的例子，例如下面的这个数组：

c
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

在遍历到数组中的第一个元素以及每个在 | 之后的元素时，candidate 都会因为 count 的值变为 0 而发生改变。最后一次 candidate 的值从 5 变为 7，也就是这个数组中的众数。

Boyer-Moore 算法的正确性较难证明，这里给出一种较为详细的用例子辅助证明的思路，供读者参考：

首先我们根据算法步骤中对 count 的定义，可以发现：在对整个数组进行遍历的过程中，count 的值一定非负。这是因为如果 count 的值为 0，那么在这一轮遍历的开始时刻，我们会将 x 的值赋予 candidate 并在接下来的一步中将 count 的值增加 1。因此 count 的值在遍历的过程中一直保持非负。

那么 count 本身除了计数器之外，还有什么更深层次的意义呢？我们还是以数组

c
[7, 7, 5, 7, 5, 1 | 5, 7 | 5, 5, 7, 7 | 7, 7, 7, 7]

作为例子，首先写下它在每一步遍历时 candidate 和 count 的值：

c
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

我们再定义一个变量 value，它和真正的众数 maj (这个例子里就是7)绑定。在每一步遍历时，如果当前的数 x 和 maj 相等，那么 value 的值加 1，否则减 1。value 的实际意义即为：到当前的这一步遍历为止，众数出现的次数比非众数多出了多少次。我们将 value 的值也写在下方：

c
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

有没有发现什么？我们将 count 和 value 放在一起：

c
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

发现在每一步遍历中，count 和 value 要么相等，要么互为相反数！并且在候选众数 candidate 就是 maj 时，它们相等，candidate 是其它的数时，它们互为相反数！

为什么会有这么奇妙的性质呢？这并不难证明：我们将候选众数 candidate 保持不变的连续的遍历称为「一段」。在同一段中，count 的值是根据 candidate == x 的判断进行加减的。那么如果 candidate 恰好为 maj，那么在这一段中，count 和 value 的变化是同步的；如果 candidate 不为 maj，那么在这一段中 count 和 value 的变化是相反的。因此就有了这样一个奇妙的性质。

这样以来，由于：

  • 我们证明了 count 的值一直为非负，在最后一步遍历结束后也是如此；
  • 由于 value 的值与真正的众数 maj 绑定，并且它表示「众数出现的次数比非众数多出了多少次」，那么在最后一步遍历结束后，value 的值为正数；

在最后一步遍历结束后，count 非负，value 为正数，所以它们不可能互为相反数，只可能相等，即 count == value。因此在最后「一段」中，count 的 value 的变化是同步的，也就是说，candidate 中存储的候选众数就是真正的众数 maj。

c++代码：

c
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = -1;
        int count = 0;
        for (int num : nums) {
            if (num == candidate)
                ++count;
            else if (--count < 0) {
                candidate = num;
                count = 1;
            }
        }
        return candidate;
    }
};

Java代码：

java
class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int x = -1, cnt = 0;
        for (int i : nums) {
            if (cnt == 0) {
                x = i;
                cnt = 1;
            } else {
                cnt += x == i ? 1 : -1;
            }
        }
        cnt = 0;
        for (int i : nums) if (x == i) cnt++;
        return cnt > n / 2 ? x : -1;
    }
}
  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)

摩尔投票推广到 n / k 的情况 ​

题目描述 ​

Leetcode 229. 多数元素 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。

示例 1：

输入：nums = [3,2,3]
输出：[3]

示例 2：

输入：nums = [1]
输出：[1]

示例 3：

输入：nums = [1,2]
输出：[1,2]

提示：

  • 1 <= nums.length <= 5 * 10^4
  • -10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。

哈希表计数 ​

一个朴素的做法是使用「哈希表」进行计数，在计数完成后将所有出现次数超过n/3 的元素加入答案。

Java代码

java
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer> map = new HashMap<>();    
        for (int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        List<Integer> ans = new ArrayList<>();
        for (int i : map.keySet()) {
            if (map.get(i) > n / 3) ans.add(i);
        }
        return ans;
    }
}

c++代码

c
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        unordered_map<int, int> cnt;

        for (auto & v : nums) {
            cnt[v]++;
        }
        for (auto & v : cnt) {
            if (v.second > n / 3) {
                ans.push_back(v.first);
            }
        }

        return ans;
    }
};
  • 时间复杂度：\(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 最终没有成为候选者。

有两种可能会导致这个结果：

  1. 数值 x从来没成为过候选者：

如果 x 从来没成为过候选者，那么在遍历 x 的过程中，必然有 k - 1 个候选者被减了超过 n / k 次（每遇到x都会被减一次），假设当前 x 出现次数为 C，已知 C > n / k，此时总个数为

\((k−1)∗C+C=C∗k\)

再根据 \(C > n / k\)，可知\( C * k > n\)，而我们总共就只有 \(n\) 个数，因此该情况恒不成立。

  1. 数值 x成为过候选者，但被逐出替换了：

同理，被逐出替换，说明发生了对 x 出现次数减一的动作（减到 0），每次的减一操作，意味着有其余的 k - 2 个候选者的出现次数也发生了减一动作，加上本身被遍历到的当前数 num[i]（即最终把x换出的数字），共有 k - 1 个数字的和 x 被一同统计。

因此，根据我们摩尔投票的处理过程，如果 x 成为过候选者，并被逐出替换，那么同样能够推导出我们存在超过 n 个数。

综上，如果存在出现次数超过 \(n / k\)的数，其必然会成为 \(k - 1\)个候选者之一。

c++代码：

c
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        vector<int> ans;
        int element1 = 0;
        int element2 = 0;
        int vote1 = 0;
        int vote2 = 0;

        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
                vote1++;
            } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
                vote2++;
            } else if (vote1 == 0) { // 选择第一个元素
                element1 = num;
                vote1++;
            } else if (vote2 == 0) { // 选择第二个元素
                element2 = num;
                vote2++;
            } else { //如果三个元素均不相同，则相互抵消1次
                vote1--;
                vote2--;
            }
        }

        int cnt1 = 0;
        int cnt2 = 0;
        for (auto & num : nums) {
            if (vote1 > 0 && num == element1) {
                cnt1++;
            }
            if (vote2 > 0 && num == element2) {
                cnt2++;
            }
        }
        // 检测元素出现的次数是否满足要求
        if (vote1 > 0 && cnt1 > nums.size() / 3) {
            ans.push_back(element1);
        }
        if (vote2 > 0 && cnt2 > nums.size() / 3) {
            ans.push_back(element2);
        }

        return ans;
    }
};

Java代码：

java
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int n = nums.length;
        int a = 0, b = 0;
        int c1 = 0, c2 = 0;
        for (int i : nums) {
            if (c1 != 0 && a == i) c1++;
            else if (c2 != 0 && b == i) c2++;
            else if (c1 == 0 && ++c1 >= 0) a = i;
            else if (c2 == 0 && ++c2 >= 0) b = i;
            else {
                c1--; c2--;
            }
        }
        c1 = 0; c2 = 0;
        for (int i : nums) {
            if (a == i) c1++;
            else if (b == i) c2++;
        }
        List<Integer> ans = new ArrayList<>();
        if (c1 > n / 3) ans.add(a);
        if (c2 > n / 3) ans.add(b);
        return ans;
    }
}
  • 时间复杂度：\(O(n)\)
  • 空间复杂度：\(O(1)\)

用心记录，持续成长

Copyright © 2026 hswsp