题目描述

他让redbag找众数

他还特意表示,这个众数出现次数超过了一半

一共n个数,而且保证有

n<=2000000

而且每个数<2^31-1

时间限制 1s

空间限制 3.5M(你没看错3.5M)（实际后来改成了5M）

 

题解：

一眼众数感觉很水，直接存下来，sort一下，然后统计连续出现次数

但是5M？？？

发现，2000000的空间开不下， 但是可以开下一半？？

然后就先输入前1000000个。sort，记录出现次数最多的数，和它的出现次数。

再输入剩下的，sort，记录出现次数最多的数，和它的出现次数。

两者出现次数较大的就是众数。

证明？？

题目关键：众数出现次数超过一半。

说明，两个最多的数一定至少有一个是那个众数。然后，最多数不是众数的那个，一定不如另一个是众数的数出现次数多。

就可以做了。

代码：

#include
     
      using namespace std;const int N=1000000+2;int a[N];int mx1,num1,tot;int mx2,num2;int n;int main(){    scanf("%d",&n);    for(int i=1;i<=n/2;i++){        scanf("%d",&a[i]);    }    sort(a+1,a+n/2+1);    for(int i=1;i<=n/2;i++){        tot=1;        while(i+1<=n/2&&a[i]==a[i+1]){            tot++;i++;        }        if(tot>mx1) mx1=tot,num1=a[i];    }    for(int i=1;i<=n-n/2;i++){        scanf("%d",&a[i]);    }    sort(a+1,a+n-n/2+1);    for(int i=1;i<=n-n/2;i++){        tot=1;        while(i+1<=n-n/2&&a[i]==a[i+1]){            tot++;i++;        }        if(tot>mx2) mx2=tot,num2=a[i];    }    if(mx1
     

 

原题3.5M就不行了。

但是，还有什么摩尔投票法。很机智。连1000000数组也不用。

开一个房子，进去一个数，如果房子里没有数，就打上它的标记。

如果房间里的数相同，cnt++

如果不同，带走一个这个数。即cnt--

最后剩下的一定是众数。

因为占比过半，所以为所欲为啊。

代码就不贴了。