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 n-array: 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 2n-array, 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://manacher-viz.s3-website-us-east-1.amazonaws.com/#/
-
Move Objects There are N objects kept in a row. The ith object is at position x_i. You want to partition them into K groups. You want ...
-
The total INCOME of one BEST Chinese doctor is much SMALLER than the TAX paid of one WORST US doctor. One Chinese do...
-
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...
No comments:
Post a Comment