Connor

Connor的折腾笔记

0%

求众数——Moore投票法

发表于 更新于 分类于
遇到一道有趣的题目和有趣的方法：使用Moore 摩尔投票法，线性时间求解 Majority Vote Algorithm 问题。

169. 求众数 求超过 ⌊ n/2 ⌋ 次的元素

简单

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

1
2
输入：[3,2,3]
输出：3

示例 2：

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

进阶：

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

Moore投票法介绍

参考

首先我们了解下什么是摩尔投票法:其基于一个事实: 当数组中存在某个数个数大于数组长度的1/2 时，我们可以使用使用摩尔投票法找出这个数。

算法：设置一个候选人和一个计数器 count。遍历数组，每次遇到和候选人一样的值则 ++count，否 则 --count 。当 count == 0 时替换候选人。最后剩下的就是我们所求的众数。

那么为什么能这样求呢？首先我们可以把数组中的数分为两类：众数和其他数。 算法中遇到和候选人不一样的值进行 --count 时其实可以看成一次互拼。而我们必须要保证这个互拼只有以下2种情况：

  1. 众数和其他数互拼，两者同时消耗1.
  2. 其他数和其他数互拼，其他数消耗2.

如果我们想要最后剩下的都是众数，那么按照对众数最不利的情况是所有的互拼都是情况1。而由于众数的个数大于 \(\lfloor n / 2 \rfloor\)，所以最不利的情况最后留下来的也是众数。

而在算法中我们保证互拼只有以上2种情况的方法就是：我们遇到相同的候选人则 ++count，这样可以避免众数和众数互拼（因为众数肯定是相等的，所以相同的时候 ++count 就避免了众数和众数互拼）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int majorityElement(vector<int>& nums) {
    // 摩尔投票
    int count = 1;
    int major = nums[0];
    for (int i = 1; i < nums.size(); ++i) {
        if (major == nums[i])
            ++count;
        else {
            --count;
            if (count == 0) 
                major = nums[i + 1];
        }
    }
    return major;
}

229. 求众数 II 求超过 ⌊ n/3 ⌋ 次的元素

中等

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

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

示例 1：

1
2
输入：[3,2,3]
输出：[3]

示例 2：

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

示例 3：

1
2
输入：[1,1,1,3,3,2,2,2]
输出：[1,2]

提示：

  • 1 <= nums.length <= 5 * 104
  • -109 <= nums[i] <= 109

Moore投票进阶版——求超过 ⌊ n/3 ⌋ 次的元素

区别：

  • 求超过 ⌊ n/3 ⌋ 次的元素最多有两个，所以我们可以改变思路寻找两个众数，将三个不同的元素放在一起对碰，具体方法如下：

  1. 有别于原版的Moore投票，因为至多可能有两个元素符合要求，所以需要两个元素的值及计数器；

  2. 比较时首先比较当前元素是否等于两个当前计数的元素，若相等，对应计数器 + 1；

  3. 若都不相等，分两种情况：

    • 有值为0的计数器

      将更新元素为当前元素，++count；

    • 两个计数器均不为0

      两个计数器分别 - 1，三个不同元素一组消消乐。

  4. 最后计数检查留下来的元素出现次数是否符合要求，符合则压入数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
vector<int> majorityElement(vector<int>& nums) {
    int res1 = nums[0]; 
    int res2 = nums[0];
    int count1 = 0;
    int count2 = 0;
	// Moore投票 双候选人版
    for (int i : nums) {
        if (i == res1)
            ++count1;
        else if (i == res2)
            ++count2;
        else if (count1 == 0) {
            res1 = i;
            ++count1;
        }
        else if (count2 == 0) {
            res2 = i;
            ++count2;
        }
        else {
            --count1;
            --count2;
        }
    }
	// 统计结果的两个元素的出现次数
    count1 = 0;
    count2 = 0;
    for (int i : nums) {
        if (i == res1)
            ++count1;
        else if (i == res2)
            ++count2;
    }
	// 将超过 ⌊ n/3 ⌋ 的元素加入数组
    vector<int> res;
    if (count1 > nums.size() / 3)
        res.push_back(res1);
    if (count2 > nums.size() / 3) 
        res.push_back(res2);

    return res;
}

Moore投票法总结

优势：

  • \(O(n)\) 的时间复杂度 \(O(1)\) 的空间复杂度

限制条件：

  • 限制众数出现的次数要在某个比例之上，且需要提前知道这个比例，若数组中众数出现次数小于这个比例，则不能正常求解。