「BZOJ 2456」mode - 乱搞

给你一个个数的数列，其中某个数出现了超过次即众数，请你找出那个数。

链接

题解

的数据，内存是存不下的，考虑空间复杂度为的做法。

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

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

代码

#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;
}