跳转至

主元素问题

概述

给一个有 \(n\) 个元素的数列，保证有一个数 \(a\) 出现的次数 超过 \(\dfrac n 2\)，求这个数。

做法

排序做法

显然，若一个数列存在主元素，那么这个主元素在排序后一定位于 \(\dfrac{n}{2}\) 的位置。

1
2
sort(a, a + n);
cout << a[n / 2];

时间复杂度是 \(O(n\log n)\)。

桶计数做法

另一个自然的思路是计数数列中各数的出现次数，出现次数大于 \(\dfrac n 2\) 的就是主元素。我们创建一个桶来存储出现次数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
constexpr int m = 30000;  // 与数的取值范围相对应
int ans[m] = {0};         // 也可选择使用 std::unordered_map<int, int>

for (int i = 0; i < n; i++) {
  cin >> t;
  ans[t]++;
  if (ans[t] > n / 2) {
    cout << t;
    break;
  }
}

时间复杂度 \(O(n)\)，这很好；但空间复杂度较大。能不能把空间复杂度降下来呢？

下面介绍本问题的 \(O(n)\) 时间复杂度、\(O(1)\) 空间复杂度解法。

摩尔投票算法

由于主元素的出现的次数超过 \(\dfrac n 2\)，那么在不断消掉两个不同的元素之后，最后一定剩下主元素。

由于我们只需要关心元素的值而不关心其位置，故可用 val 和 cnt 两个变量代替完整存储元素。

1
2
3
4
5
6
7
int val = -1, cnt = 0;
while (n--) {
  cin >> x;
  if (!cnt) val = x;
  (val == x) ? ++cnt : --cnt;
}
cout << val;

注意

若原数据中并不存在主元素，则摩尔投票算法给出的结果可能是任意值。此时需要再次遍历一遍数组，统计 val 出现次数的最大值，判断是否超过 \(\dfrac n 2\)。

另外，为了保证空间复杂度为 \(O(1)\)，再次遍历数组时可以选择重置输入位置指示器，可利用 std::basic_istream<CharT,Traits>::seekg（流式输入）或 rewind、fseek（C 风格输入）等库函数。

习题

进阶：试着基于摩尔投票算法略做调整，找到出现次数严格大于 ⅓ 的元素？

LeetCode 229. 多数元素 II

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

实现 
 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
class Solution {
 public:
  vector<int> majorityElement(vector<int>& nums) {
    // 将摩尔投票算法的「抵消2个不同元素」变为「抵消3个两两不同的元素」

    constexpr int SENTINEL = 1e9 + 1;  // -1e9 <= nums[i] <= 1e9
    int n = nums.size();

    int maj1 = SENTINEL, maj2 = SENTINEL;
    int cnt1 = 0, cnt2 = 0;
    for (auto num : nums) {
      if (num == maj1) {
        ++cnt1;
      } else if (num == maj2) {
        ++cnt2;
      } else if (cnt1 == 0) {
        maj1 = num;
        ++cnt1;
      } else if (cnt2 == 0) {
        maj2 = num;
        ++cnt2;
      } else {
        --cnt1;
        --cnt2;
      }
    }

    // 由于题目没有保证存在2个超过 ⌊ n/3 ⌋ 次的元素，故需检验
    vector<int> ans;
    cnt1 = 0, cnt2 = 0;
    for (auto num : nums) {
      if (num == maj1)
        ++cnt1;
      else if (num == maj2)
        ++cnt2;
    }
    if (cnt1 > n / 3) ans.push_back(maj1);
    if (cnt2 > n / 3) ans.push_back(maj2);

    return ans;
  }
};

参考

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：SDLTF, Ethkuil
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用