跳转至

主元素問題

概述

給一個有 \(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;
  }
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：SDLTF
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用