题目描述
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数<2^31-1
时间限制 1s
空间限制 3.5M(你没看错3.5M)（实际后来改成了5M）
题解：
一眼众数感觉很水，直接存下来，sort一下，然后统计连续出现次数
但是5M？？？
发现，2000000的空间开不下， 但是可以开下一半？？
然后就先输入前1000000个。sort，记录出现次数最多的数，和它的出现次数。
再输入剩下的，sort，记录出现次数最多的数，和它的出现次数。
两者出现次数较大的就是众数。
证明？？
题目关键：众数出现次数超过一半。
说明，两个最多的数一定至少有一个是那个众数。然后，最多数不是众数的那个，一定不如另一个是众数的数出现次数多。
就可以做了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=+;
int a[N];
int mx1,num1,tot;
int mx2,num2;
int n;
int main()
{
scanf("%d",&n);
for(int i=;i<=n/;i++){
scanf("%d",&a[i]);
}
sort(a+,a+n/+);
for(int i=;i<=n/;i++){
tot=;
while(i+<=n/&&a[i]==a[i+]){
tot++;i++;
}
if(tot>mx1) mx1=tot,num1=a[i];
}
for(int i=;i<=n-n/;i++){
scanf("%d",&a[i]);
}
sort(a+,a+n-n/+);
for(int i=;i<=n-n/;i++){
tot=;
while(i+<=n-n/&&a[i]==a[i+]){
tot++;i++;
}
if(tot>mx2) mx2=tot,num2=a[i];
}
if(mx1<mx2) swap(num1,num2);
printf("%d",num1);
return ;
}
原题3.5M就不行了。
但是，还有什么摩尔投票法。很机智。连1000000数组也不用。
开一个房子，进去一个数，如果房子里没有数，就打上它的标记。
如果房间里的数相同，cnt++
如果不同，带走一个这个数。即cnt--
最后剩下的一定是众数。
因为占比过半，所以为所欲为啊。
代码就不贴了。