how to choose the num ???

[micheal_sunny]

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

[micheal_sunny]

it is form other online judge that is called zoj
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^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

[misof]

There is a tricky solution that only needs O(1) memory and O(N) time.

And there is the standard solution: load all numbers into memory, and find the median. Is there a memory limit such that this second solution won't work?

[micheal_sunny]

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

[tobby]

I think you may make use of this fact:

it is assumed that there is a number X which has more than L / 2 instances in A

[misof]

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

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?

[Planeyang]

Well, It doesn't make sence to me.

Yeah,If there are over L/2 number the same. the midpoint is the number X.But how what can I do if less than L/2? Divide&conquer? I don't know how to do.


And, I really wanna know how to do it with space O(1) and time O(N)?

[Timo]

freq = 0

while read number
if freq == 0 then answer = number
else
if number == answer then freq=freq+1
else freq=freq-1
end while

output answer

[misof]

But how what can I do if less than L/2? Divide&conquer? I don't know how to do.

In this case you should RTFP (Read The Fine Problem statement)
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 comparison-based model, i.e., without using any special properties of the elements)

[micheal_sunny]

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

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);
}

[Planeyang]

sorry about my careless.
Thank you misof and Timo

The Program of Timo is really cool!
That's a very good idea.

[Timo]

sorry about my careless.
Thank you misof and Timo

The Program of Timo is really cool!
That's a very good idea.

the idea was come from misof

[micheal_sunny]

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);
	}
}

always wa....

[micheal_sunny]

i use int instead of long
i got ac
can anyone tell me why?

Thanks , all of you~~~