how to choose the num ???
Moderator: Board moderators

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am
how to choose the num ???
there is a sequence like 1,4,1,3,4,9,2,4
i wanted to choose "4",because '4' appear 3 times , other numbers are less than 3
i don't konw whether i tell the problem clearly
i give a sample again
5 9 1 6 5
i want "5"
can anyone tell me how to solve this,thank you very much
sorry for my poor english
i wanted to choose "4",because '4' appear 3 times , other numbers are less than 3
i don't konw whether i tell the problem clearly
i give a sample again
5 9 1 6 5
i want "5"
can anyone tell me how to solve this,thank you very much
sorry for my poor english

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am
it is form other online judge that is called zoj
i give the description
i give the description
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^311). 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

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am
hi misof
I don't know the tricky solution which you talk about, can you tell me more ?
And you say there is the standard solution: load all numbers into memory, and find the median. can you say clearly about this, I am intertesting about what you say.
Oh, by the way :Time limit: 5 Seconds Memory limit: 1024K
I don't know the tricky solution which you talk about, can you tell me more ?
And you say there is the standard solution: load all numbers into memory, and find the median. can you say clearly about this, I am intertesting about what you say.
Oh, by the way :Time limit: 5 Seconds Memory limit: 1024K
Suppose you sort the numbers, and, as tobby said, don't forget that more than half of the numbers is the same. How can the situation look like? Can the middle element be different than X?micheal_sunny wrote:hi misof
I don't know the tricky solution which you talk about, can you tell me more ?
And you say there is the standard solution: load all numbers into memory, and find the median. can you say clearly about this, I am intertesting about what you say.
Oh, by the way :Time limit: 5 Seconds Memory limit: 1024K
In this case you should RTFP (Read The Fine Problem statement)Planeyang wrote:But how what can I do if less than L/2? Divide&conquer? I don't know how to do.
and notice that in the discussed problem you are guaranteed that the L/2 bound will hold.
In the general case finding the most frequent element cannot be done better* than Theta(n log n).
* (assuming a comparisonbased model, i.e., without using any special properties of the elements)

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am
hi timo
thanks for you idea
and i wrote it by c++ got a wa i dont know whether i dont understand what you said or there is something mistake
can you pls check it ?
The sample is right
thanks for you idea
and i wrote it by c++ got a wa i dont know whether i dont understand what you said or there is something mistake
can you pls check it ?
The sample is right
Code: Select all
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long feq,a;
long ans,test;
while (scanf("%ld",&test) != EOF)
{
feq =0;
for (int i=0;i<test;i++)
{
scanf("%ld",&a);
if (feq ==0)
{
ans = a;
}
else
{
if (a == ans) feq ++;
else feq;
}
}
printf("%ld\n",ans);
}
Last edited by micheal_sunny on Thu Oct 19, 2006 6:48 am, edited 1 time in total.

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am
Code: Select all
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
long long feq,a;
long long ans,test;
while (scanf("%lld",&test)!=EOF)
{
feq =0;
ans=0;
for (int i=0;i<test;i++)
{
scanf("%lld",&a);
if (feq ==0)
{
ans = a;
}
else
{
if (a == ans)
{
feq ++;
}
else
feq;
}
}
printf("%lld\n",ans);
}
}

 New poster
 Posts: 7
 Joined: Sat Oct 14, 2006 11:24 am