I meet this question in an interview. It is actually a famous problem, whose solution is available here .
Here my thinking is provided.
1, The simplest case, suppose there are four elements, a,b,c,d, the minimum number of comparisons is 4:
a < b, c < d > b < d > max(b,c) is the second largest element.
That is, we compare (a,b), (c,d) to get the largest values b,d, then find the largest value d, the second largest value is in the set of all elements that have been compared with d, that is, b or c.
2, Suppose we have 2n elements: (a,b), (c,d), (e,f), ....... We have n pairs, so select the larger element in each pair to form an narray: b,d,f....In total n comparison is needed.
Suppose our algorithm can find the largest two values from b,d,f,...., which is (b,d) with b < d, for example.
The second largest element can either be b or c, compare b vs c we get the second largest element.
Thus, if x(2n) is the number of comparisons needed for an 2narray, we have x(2n) = n + x(n) + 1
Solve this recursive function with x(4) = 4, we get x(n) = n + log2(n)  2.
Subscribe to:
Post Comments (Atom)
Manacher's Longest Palindromic Substring Algorithm
http://manacherviz.s3websiteuseast1.amazonaws.com/#/

Imaging you are a 40 years' old truck driver living in Illinois. You have a wonderful family and two beautiful kids. You loan a...

Given n nonnegative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap aft...

The total INCOME of one BEST Chinese doctor is much SMALLER than the TAX paid of one WORST US doctor. One Chinese do...
No comments:
Post a Comment