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.
Thursday, October 10, 2013
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 non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap aft...
There is only one ultimate solution for expensive medical system in US: hire more doctors from China!!! Set up strict exams to maintain the qualityThe total INCOME of one BEST Chinese doctor is much SMALLER than the TAX paid of one WORST US doctor. One Chinese do...