主元素问题

概述

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

做法

桶计数做法

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

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} 的位置。

那么我们又有想法了：

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

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

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

主元素数列的特性

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

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

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) 。

int val = -1, cnt = 0;
while (n--) {
  scanf("%d", &a);
  if (a != val) {
    if (--cnt <= 0) {
      val = a, cnt = 1;
    }
  } else {
    ++cnt;
  }
}
buildLast update and/or translate time of this article，Check the history
editFound smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github
peopleContributor of this article SDLTF
translateTranslator of this article Visit the original article!
copyrightThe article is available under CC BY-SA 4.0 & SATA ; additional terms may apply.

Comments