主元素问题

概述

给一个有 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;
    }
}

评论