「BZOJ 2456」mode - 乱搞

给你一个 n 个数的数列,其中某个数出现了超过 n \over 2 次即众数,请你找出那个数。

链接

BZOJ 2456

题解

500,000 的数据, \text {1M} 内存是存不下的,考虑空间复杂度为 O(1) 的做法。

如果众数出现了超过 n \over 2 次,那么任意删除序列中的两个不同的数,众数的出现次数仍然超过一半。不停地进行下去,最终剩下的一个数即为众数。

实现时,记录一个「当前的数」和它的「出现次数」,删除一次则出现次数减一,出现次数为 0 时用读入的数更新当前的数。

代码

#include <cstdio>

const int MAXN = 500000;

int main() {
    int n;
    scanf("%d", &n);
    int ans = -1, cnt = 0;
    for (int i = 0; i < n; i++) {
        int x;
        scanf("%d", &x);

        if (cnt == 0) {
            ans = x;
            cnt = 1;
        } else {
            if (ans == x) {
                cnt++;
            } else {
                cnt--;
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}