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/#/

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...

If I decided to invest in energy and natural resources, I will prefer Russian ETFs. Once oil prices go up, Russian stocks will go up as we...

http://manacherviz.s3websiteuseast1.amazonaws.com/#/
No comments:
Post a Comment