how to choose the num ???

Let's talk about algorithms!

Moderator: Board moderators

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

how to choose the num ???

Post by 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
New poster
Posts: 7
Joined: Sat Oct 14, 2006 11:24 am

Post by 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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by 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
New poster
Posts: 7
Joined: Sat Oct 14, 2006 11:24 am

Post by 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
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by 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
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

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
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
New poster
Posts: 9
Joined: Sun Oct 15, 2006 1:31 pm
Location: China

Post by 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
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by 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
"Life is more beautiful with algorithm"

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Post by misof »

Planeyang wrote: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
New poster
Posts: 7
Joined: Sat Oct 14, 2006 11:24 am

Post by 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);
}
Last edited by micheal_sunny on Thu Oct 19, 2006 6:48 am, edited 1 time in total.

Planeyang
New poster
Posts: 9
Joined: Sun Oct 15, 2006 1:31 pm
Location: China

Post by Planeyang »

sorry about my careless.
Thank you misof and Timo

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

Timo
Learning poster
Posts: 70
Joined: Tue Oct 11, 2005 2:44 am
Location: Indonesia

Post by Timo »

Planeyang wrote: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 :D
"Life is more beautiful with algorithm"

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

Post by 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
New poster
Posts: 7
Joined: Sat Oct 14, 2006 11:24 am

Post by micheal_sunny »

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

Thanks , all of you~~~ :) :)

Post Reply

Return to “Algorithms”