题目;
--------------------------------------------------------------------------------
The Most Frequent Number
--------------------------------------------------------------------------------
Time limit: 5 Seconds Memory limit: 1024K
Total Submit: 3123 Accepted Submit: 862
--------------------------------------------------------------------------------
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>
int main()
{
double long nNum1 = '#';
double long nNum2 = '#';
long nCount = 0;
long i;
while(scanf("%ld",&i)!=EOF)
{ nCount=0;
nNum1 = '#';
nNum2 = '#';
while(i--)
{
if(nCount == 0)
{
scanf("%ld",&nNum1);
nCount++;
}
else if(nCount >= 1)
{
scanf("%ld",&nNum2);
}
if(!(nNum1=='#' || nNum2=='#'))
{
if(nNum1 == nNum2)
{
nCount++;
nNum2 = '#';
}
else
{
nCount--;
if(nCount == 0)
{
nNum1 = '#';
}
nNum2 = '#';
}
}
}
printf("%ld\n",nNum1);
}
return 0;
}
连接：
http://acm.zju.edu.cn/show_problem.php?pid=2132
请各位帮忙看看哪不对
谢谢
----------------解决方案--------------------------------------------------------
写得太长太多余了
只需要四个int变量就行了
if(!(nNum1=='#' || nNum2=='#'))这样的写法是错的
----------------解决方案--------------------------------------------------------
楼主的算法好象有问题.
这个题目应该是hash或者二叉树
我用map写了一个过了
#include<stdio.h>
#include<map>
using namespace std;
map<long ,int> mp;
int main()
{
int n,i,max;
long x;
while(scanf("%d",&n)!=EOF)
{
mp.clear();
max=0;
for(i=0;i<n;i++)
{
scanf("%d",&x);
mp[x]++;
if(mp[max]<mp[x]) max=x;
}
printf("%d\n",max);
}
return 0;
}
----------------解决方案--------------------------------------------------------
----------------解决方案--------------------------------------------------------
谢谢了
----------------解决方案--------------------------------------------------------