算法基础算法

众数，摩尔投票

字数统计: 1.9k字   |   阅读时长: 8分
, , , ,

摘要: 求众数的算法，摩尔投票

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文以 169. 多数元素 和 229. 求众数 II 来看一下求众数的算法。其中我们重点看一下摩尔投票算法。

求众数问题一般有4种主流方法：

  1. 直接开哈希表计数最容易想到，但是需要 O(N) 额外空间。
  2. 众数出现次数的下界给定的话，可以抽象成 topK 问题。
  3. 摩尔投票(多数投票)
  4. 分治法

题目1

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 $\left\lfloor\frac{n}{2}\right\rfloor$ 的元素。

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

提示：

1
2
3
n == nums.length
1 <= n <= 5 * 1e4
-1e9 <= nums[i] <= 1e9

示例 1：
输入：nums = [3,2,3]
输出：3

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

算法1：哈希表计数

两道题都一是一个流程：开哈希表，键是数组中的数字，值是数字的计数。按顺序枚举枚举数组中的数，出现的数字在哈希表对应位置的计数 +1，每次枚举都查看一次答案符合不符合条件，若符合条件则返回结果或压入 result 数组。

时间 $O(N)$ ，空间 $O(N)$。

代码(c++)

当前枚举的数字，计数加一后若 > n/2 ，则该数是答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int, int> mapping;
        for(int num: nums)
        {
            ++mapping[num];
            if(mapping[num] > n / 2)
                return num;
        }
        return -1;
    }
};

算法2：抽象成 topK

已知数组一定存在个数 > n/2 的数字，则它的第 n/2 大的数字直接就是答案。

topK 问题的主流解法是快速选择算法，思路和模板：力扣215-快速选择算法,划分树。

STL 里有 nth_element 可以直接用。还是 O(N) 时间，但是不需要 O(N) 空间了。

代码 (C++)

1
2
3
4
5
6
7
class Solution_2 {
public:
    int majorityElement(vector<int>& nums) {
        nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end());
        return nums[nums.size() / 2];
    }
};

算法3：摩尔投票

摩尔投票算法基于这个事实：每次从数组里每次选择两个不相同的数字删除掉，最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

所以算法流程就是：找不同数字，删除，找不同数字，删除，直到找不到不同数字了。删除次数最多的情况：每一次删除都是众数和另外的数，删除 n/2 - 1 次后，剩下的一定是众数，如果删的是两个另外的数，则删除的次数会减少，最终剩下的匹配不到不同数字的众数会变多。

枚举所有数字，维护候选人 cand 和计数，若新来的数与候选人相同，则 cnt++，否则 cnt—，当计数为0时，若来了新候选人，则更新候选人。

代码(c++，模板)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int cand, cnt = 0;
        for(int num: nums)
        {
            if(!cnt)
            {
                cand = num;
                cnt = 1;
                continue;
            }
            if(num == cand)
                ++cnt;
            else
                --cnt;
        }
        return cand;
    }
};

算法4: 分治法

  • 分解：将数组分为左右两部分
  • 解决：当数组长度为 1 时，可以直接解决，即众数为数组中的一个元素
  • 合并：左边的众数为 x，右边的众数为 y，若 x 和 y 不同，则需要遍历区间决定谁才是整个区间上真正的众数

算法的正确性依赖多数元素的个数大于数组元素个数的一半这个条件。

代码 (C++)

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
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        return solve(nums, 0, n - 1);
    }

private:
    int solve(const vector<int>& nums, int l, int r)
    {
        if(l == r)
            return nums[l];
        int mid = (l + r) / 2;
        int left = solve(nums, l, mid);
        int right = solve(nums, mid + 1, r);
        if(left == right)
            return left;
        int cnt_left = 0;
        int cnt_right = 0;
        for(int i = l; i <= r; ++i)
        {
            if(nums[i] == left)
                ++cnt_left;
            if(nums[i] == right)
                ++cnt_right;
        }
        if(cnt_left > cnt_right)
            return left;
        else
            return right;
    }
};

题目2

229. 求众数 II

给定一个大小为 n 的整数数组，找出其中所有出现超过 $\left\lfloor\frac{n}{3}\right\rfloor$ 次的元素。

提示：

1
2
1 <= nums.length <= 5e4
-1e9 <= nums[i] <= 1e9

示例 1：
输入：nums = [3,2,3]
输出：[3]

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

示例 3：
输入：nums = [1,2]
输出：[1,2]

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

算法1：哈希表计数

当前枚举的数字，计数加一后若 > n/3 ，则把该数压进答案数组 result，当 result 中已经压进两个数时，就可以返回结果了。

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        unordered_map<int, int> mapping;
        vector<int> result;
        for(int num: nums)
        {
            ++mapping[num];
            if(mapping[num] > n / 3 && (result.empty() || result[0] != num))
                result.push_back(num);
            if((int)result.size() >= 2)
                return result;
        }
        return result;
    }
};

算法2：抽象成 topK

先把 n/3 位置和 2n/3 位置的数字找到。这两个数字不一定是答案，但是如果答案存在，一定是这两个数之一，或者这两个数都是答案。然后枚举数组的数字，统计这两个数组的计数，确定它们是否是答案。

代码(c++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        nth_element(nums.begin(), nums.begin() + n / 3, nums.end());
        nth_element(nums.begin(), nums.begin() + 2 * n / 3, nums.end());
        int cand1 = nums[n / 3];
        int cand2 = nums[2 * n / 3];
        int cnt1 = 0, cnt2 = 0;
        vector<int> result;
        for(int num: nums)
        {
            if(num == cand1) cnt1++;
            else if(num == cand2) cnt2++;
        }
        if(cnt1 > n / 3) result.push_back(cand1);
        if(cnt2 > n / 3) result.push_back(cand2);
        return result;
    }
};

算法3：摩尔投票

前一题是有一个候选人，每次仍一个二元组；本题是有两个候选人，每次仍一个三元组(三元组里的数字均不相同)。

按顺序枚举数组中的数字，维护两个候选人 cand1, cand2 和对应的计数器 cnt1, cnt2。

当新来的数字与两个候选人都不同且两个计数器都大于零时，得到了一组都不相同的三元组，丢弃掉(—cnt1, —cnt2)。

枚举完成时，得到的两个候选人 cand1, cand2 仍需要遍历一遍计数，大于 n/3 才是答案。

摩尔投票算法是 O(N) 时间 O(1) 空间的。

代码(c++)

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
43
44
45
46
class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        if(nums.empty()) return vector<int>();
        int n = nums.size();
        int cand1, cand2;
        int cnt1 = 0, cnt2 = 0;
        vector<int> result;
        for(int num: nums)
        {
            if(num == cand1)
            {
                cnt1++;
                continue;
            }
            if(num == cand2)
            {
                cnt2++;
                continue;
            }
            if(!cnt1)
            {
                cand1 = num;
                cnt1 = 1;
                continue;
            }
            if(!cnt2)
            {
                cand2 = num;
                cnt2 = 1;
                continue;
            }
            // 此时三个元素不同，且都有数量
            cnt1--, cnt2--;
        }
        cnt1 = cnt2 = 0;
        for(int num: nums)
        {
            if(num == cand1) cnt1++;
            else if(num == cand2) cnt2++;
        }
        if(cnt1 > n / 3) result.push_back(cand1);
        if(cnt2 > n / 3) result.push_back(cand2);
        return result;
    }
};
Share