题目背景
自动上次redbag用加法好好的刁难过了yyy同学以后,yyy十分愤怒.他还击给了redbag一题,但是这题他惊讶的发现自己居然也不会,所以只好找你
题目描述
他让redbag找众数
他还特意表示,这个众数出现次数超过了一半
一共n个数,而且保证有
n<=2000000
而且每个数<2^31-1
输入输出格式
输入格式：
第一行一个整数n
第二行n个整数
输出格式：
一行,这个众数
输入输出样例
输入样例#1：
5
2 3 3 3 3
输出样例#1：
3
说明
时间限制 1s
空间限制 3.5M(你没看错3.5M)
有人想水过,但我告诉你这空间是不够的
思路
引用了洛谷上@思援弓的思路，看到题目中的2,000,000就知道直接开一个2,000,000的数组是不切实际的,更不用说好写的计数排序前半部分了,有的人想到链表,只能说这样子如果除了众数其余数皆不同就要1,000,000这么大的链表了(至此都没有用到题目给出的条件)，然后题目说众数的数目超过一半,这样就可以不是很严格地存储数和数的个数了,于是就有了以下的做法:把一个数除以某个常数,把商和余分别储存下来,最后统计最多的某个商和最多的某个余还原成众数即可(易知该众数的商和余必定大于一半的个数,而个数大于一半的数有且只有一个)
const ma=;
var i,tmp,n,aa,bb:longint;
a,b:array[..ma]of longint;
begin
readln(n);
fillchar(a,sizeof(a),);
fillchar(b,sizeof(b),);
for i:= to n do
begin
read(tmp);
inc(a[tmp mod ma]);
inc(b[tmp div ma]);
end;
for i:= to ma do
begin
if a[i]>n/ then aa:=i;
if b[i]>n/ then bb:=i;
end;
writeln(bb*ma+aa);
end.