出现次数超过一半的数字

N 久没刷题,如今已经菜的不要不要的了.

今天看到新生群里在讨论他们的作业,于是我进去看了看题目.

读完题目,嗯,懂了,就是要找 n 个数里面是否存在一个出现次数超过总数一半的数字嘛,存在则输出该数字,否则输出-1.

嗯,map 搞起,于是 TLE 之. 好丢脸有木有.

嗯,再想想?哦,排序,对了,排序嘛. 于是又 TLE 之, 坑.

终于看了看输入数据的规模, woc, N<=200W. wocccccccc

嗯,终于发现了,需要 O(n) 的算法,于是想之; O(n)? 那不就是 hash 算法了嘛,于是写之,依旧 TLE 之.

于是继续想方法; woc,想不出来了,好菜啊……

于是 google 之,得一算法,嗯,如下:

首先记录两个变量: times = 0, X = 0.
循环: 遍历每一个数字 A[i],执行该语句 times==0? {times=1, X=A[i]}:{A[i]==X? times++:times--;}

最后得到的结论是: 当存在出现次数超过总次数一半的数字,那么一定是 X; 因此最后只需要再判断 X 出现的次数是否超过总数的一半即可.

最后的最后再贴一下代码吧.

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char const *argv[]){
        long long luckNumber=0;
        int n, i, times;
        scanf("%d", &n);
        long long *A = (long long *)malloc(n*sizeof(long long));
        for( times = i = 0; i < n; ++ i ) {
                scanf("%lld", A+i);
                if(times==0){ luckNumber = A[i]; times=1; }
                else {
                        if(A[i]==luckNumber){ ++times; }
                        else { --times; }
                }
        }
        for ( times = i = 0; i < n; ++ i ) {
                if(A[i]==luckNumber) {
                        ++times;
                }
        }
        if(times>=n/2) { printf("%lld\n", luckNumber); }
        else { printf("-1\n"); }
        free(A);
        return 0;
}