OJ Board

I know we can find min number in n-1
but how can we find the second min number in n + lg(n) -2

It is a question in Introduce to Algorithm (9.1-1)

Did anyone have idea of this ?

Best wishes,
Peter

I am not sure but I think you can use a array of size 2;

And when going through the data as you used for the min value lookin for the next smallest and now do the same but keep them in that 2 sized array. Here you have to check the two values only for finding the 2nd min........

Is that you asked for ???

The tournament method.

Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?

arnsfelt wrote:The tournament method.

Picture an essentially complete binary tree with all elements at the leaves and at a node having the minimum of the elements at its sons.
Now where can the second min number be in this tree ?

Could you please explain it in details

Hi Moni,

cant you just keep track of the two smallest numbers you find? like this:

You can't just go through linearly and keep track of the 2 smallest because that can use 2n - 3 comparisons in the worst case.

The tournament method works like this. First, assume n is a power of 2. Split all the elements up into arbitrary pairs. Do a comparison on each of the n/2 pairs, and then take the "winners" of each pair. Repeat until you have an overall winner (the smallest element). This requires n-1 comparisons, and there are exactly lg(n) rounds. Also, for each element, keep a list of which numbers it beats.

Now, the second smallest must have been beaten by the smallest. So just scan through the list of elements beaten by the smallest, and find the minimum value in this list. The list has lg(n) elements, so this takes lg(n) - 1 comparisons. Therefore, the total # of comparisons is always n - 1 + lg(n) - 1 = n + lg(n) - 2 ccomparisons.

On a somewhat related note, CLR also describes how to find the k-th smallest element in an array in O(n) time.

Welcome! Bugz! in uva forum!

I knew that but about the problems with those complexity and that "Tournament method" with the tree and it's child.........

Thanks to Lars for his little briefing.........

Lars Hellsten wrote: Now, the second smallest must have been beaten by the smallest. So just scan through the list of elements beaten by the smallest, and find the minimum value in this list. The list has lg(n) elements, so this takes lg(n) - 1 comparisons. Therefore, the total # of comparisons is always n - 1 + lg(n) - 1 = n + lg(n) - 2 ccomparisons.

This is an intreasting solution but I think it is not a good idea. It could be fast but it waste a lot of memory. To list all elements that are beaten by each number took n*n/2 elements! This mean that you'll get out of memory very soon (about on 100000 elements).
This is my idea:

use an binary tree. Don't care about elements that should stay on the right of root and cut the root every time the length reach 3.
The second minimun number is the final root.

i.e.

8 6 9 4 5


' ' 8
' /
6

9 should be at the right of 8 so don't care about it

' ' ' 8
' ' /
' 6
' /
4

cut 8, so 6 becomes the new root

' ' 6
' /
4

5 should be at the right of 4, so it will be swapped with 6 and becames the root

' ' 6
' /
4
' \
' ' 5

' ' 5
' /
4

At the end the number we are looking for is the root.

What do you think about it?

Mattia

matt80 wrote:
This is an intreasting solution but I think it is not a good idea. It could be fast but it waste a lot of memory. To list all elements that are beaten by each number took n*n/2 elements! This mean that you'll get out of memory very soon (about on 100000 elements).
This is my idea:
...
What do you think about it?

Mattia

Ok, I have misunderstood.
Now I can see your solution doesn't need so much memory.
Therefore mine is just a version of the bugzpodder's algorithm.
Mattia

[quote="peterlin"]I know we can find min number in n-1
but how can we find the second min number in n + lg(n) -2

It is a question in Introduce to Algorithm (9.1-1)

Did anyone have idea of this ?

Best wishes,
Peter[/quote]

Depending on the nature of the numbers, the problem can be solved with a cost in the order of O(n), if all de numbers belong to a range, and there is no one number missing in the range.

Another approach, a bit risky is to modify the Quick Sort working with the smallest numbers each time. At the risk of taking the smallest as the pivot.

if I am using the tournament algo, what happens if I have repeated numbers, and during the random pairs comparison i might compare let's say, 2 (x) and 2 (y). then it will say that (if x > y comparison is used) the second 2 (y) beat the first 2 (x) - now assuming that all the other numbers are greater than 2, then the algo isn't going to give the right answer, or did i misunderstand something?
also, just an idea: is it possible to speed up the algo to finish in linear time (assuming that somehow we took care of the problem mentioned before) this way? (for all who read the post before I re-edited it: I was at work, made the entry in a a hurry, sorry for writing that silly statement)
[c]int numbers[MX] = {n numbers };
int i = 0,
j = n - 1;

while(j > 1) {
while(i < j) {
/* numbers always contains the smaller number */
if(numbers > numbers[j]) numbers = numbers[j];
i++;
j--;
}
i = 0;
}[/c]
I haven't tested the code yet, you might need to make a j++; after the i = 0, but I hope the idea is clear - at the end, the smallest number is at numbers[0] and the second smallest is at numbers[1]
please, give feedback!
zsepi