主元素问题

概述

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

做法

桶计数做法

桶计数做法是出现一个数，就把这个数出现次数 +1 ，很好懂：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
for (int i = 0; i < n; i++) {
  cin >> t;
  ans[t]++;
}
for (int i = 0; i < m; i++) {  // m 为桶的大小
  if (ans[i] > n / 2) {
    cout << i;
    break;
  }
}

时间复杂度 O(n+m) 。

但是这个做法很浪费空间，我们不推荐使用。

排序做法

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

那么我们又有想法了：

1
2
sort(a, a + n);
cout << a[n / 2 - 1];  //因为这里数组从 0 开始使用，所以需要 -1

看起来不错！ O(n\log n) 的复杂度可还行？

下面介绍本问题的 O(n) 解法。

主元素数列的特性

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

输入时判断与上一次保存的输入是否相同，如不同则删除两数，这里用栈来实现。

1
2
3
4
5
6
while (n--) {
  scanf("%d", &a);
  q[top++] = a;
  top = (top > 1 && (q[top - 1] != q[top - 2])) ? (top - 2) : top;
}
printf("%d", q[top - 1]);

再进行优化后，空间复杂度也可以降至 O(1) 。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int val = -1, cnt = 0;
while (n--) {
  scanf("%d", &a);
  if (a != val) {
    if (--cnt <= 0) {
      val = a, cnt = 1;
    }
  } else {
    ++cnt;
  }
}
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：SDLTF
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论