--------------------------------------------------------------------------------
The Most Frequent Number
--------------------------------------------------------------------------------
Time limit: 5 Seconds Memory limit: 1024K
Total Submit: 3101 Accepted Submit: 856
--------------------------------------------------------------------------------
Seven (actually six) problems may be somewhat few for a contest. But I am really unable to devise another problem related to Fantasy Game Series. So I make up an very easy problem as the closing problem for this contest.
Given a sequence of numbers A, for a number X if it has the most instances (elements of the same value as X) in A, then X is called one of the most frequent numbers of A. Now a sequence of numbers A of length L is given, and it is assumed that there is a number X which has more than L / 2 instances in A. Apparently X is the only one most frequent number of A. Could you find out X with a very limited memory?
Input
Input contains multiple test cases. Each test case there is one line, which starts with a number L (1 <= L <= 250000), followed by L numbers (-2^31 ~ 2^31-1). Adjacent numbers is separated by a blank space.
Output
There is one line for each test case, which is the only one most frequent number X.
Sample Input
5 2 1 2 3 2
8 3 3 4 4 4 4 3 4
Sample Output
2
4
--------------------------------------------------------------------------------
Author: CHEN, Shixi (xreborner)
Homepage: http://fairyair.yeah.net/
The worst epilogue of fate. The end of all.
--------------------------------------------------------------------------------
Problem Source: Online Contest of Fantastic Game
--------------------------------------------------------------------------------
Submit Back Status
--------------------------------------------------------------------------------
Zhejiang University Online Judge V1.0 Book
#include<stdio.h>
#include<string.h>
main()
{
int n;
int max;
int i,j,count;
long a[250000];
while(scanf("%d",&n)!=EOF)
{ for(j=0;j<n;j++)
scanf("%ld",&a[j]);
for(j=0;j<n;j++)
{
count=1;
for(i=0;(i<n)&&(i!=j);i++)
{
if(a[i]==a[j])
count++ ;
}
if(count>n/2)
{max=j;break;}
}
printf("%ld\n",a[max]);
}
}
情各位帮帮忙
----------------解决方案--------------------------------------------------------
怎么改
----------------解决方案--------------------------------------------------------
不需要 250000的数组，要动态分配malloc可以减少内存使用！！
----------------解决方案--------------------------------------------------------
不需要 250000的数组，要动态分配malloc可以减少内存使用！！
一样超内存
----------------解决方案--------------------------------------------------------
这个题感觉时间很充足，就是内存少，出题人的意思应该是不能先读取了所有数据再处理，
要你边输入就得边处理，有相同的就要合并且记录下来重复多少个。
按照这个内存量，测试数据里应该有大量重复的。不妨尝试一下插入排序（读一个插入一个）
最坏虽然O(n^2)，但重复很多的时候运行时间一样会很快。
----------------解决方案--------------------------------------------------------
还有一个明显特点就是要输入的那个数必定重复了超过n/2次，
说明那个数组只要开楼主的一半大小就足够了
[此贴子已经被作者于2007-8-10 2:27:41编辑过]
----------------解决方案--------------------------------------------------------
谢谢
----------------解决方案--------------------------------------------------------
a[125000]仍然超的
----------------解决方案--------------------------------------------------------
我觉得O(n)的时间,O(1)的内存足以。你们再讨论一会吧，要是没人想出来更好的凌晨我过来说我的算法
----------------解决方案--------------------------------------------------------
能不能吧链接发出来啊？
----------------解决方案--------------------------------------------------------