Interview Algorithm: Find the Two Largest Elements in an Array of Size n

Question

This is a question of an interview that I saw on the Internet, and I'm not sure that I have the right idea.

The problem is here:

Create an algorithm to search for the two largest elements in a sequence of n numbers. The number of comparisons should be n + O (log n)

I think I would choose quick sort and stop when there are two of the biggest elements? But not 100% sure of this. Anyone have an idea about this, please share

Answer 1

Recursively split the array, find the largest element in each half, then find the largest element with which the largest element was compared. This first part requires n comparisons; the last requires O (log n). Here is an example:

1 2 5 4 9 7 8 7 5 4 1 0 1 4 2 3 2 5 9 8 5 1 4 3 5 9 5 4 9 5 9 

At each step, I combine the adjacent numbers and take the larger of the two. Compared to (5, 5, 8, 7), we see that the largest of them is 8, and if we look at each number that was compared with 9 (5, 5, 8, 7), it should be second largest in the array. Since this has O (log n) levels, this will require O (log n).

Answer 2

For only 2 , a normal choice can be good enough. it is basically O (2 * n).

For the more general question, “select k elements from the size of the array n” quick Sort is good thinking, but you don't really need to sort the entire array.

try it

• you select the anchor point, split the array into N [m] and N [nm].
• if k <m, forget the part N [nm], perform step 1 in N [m].
• if k> m, forget the part N [m], take a step in N [nm]. This time you will try to find the first element km in N [nm].
• If k = m, you got it.

Basically, like locate k in an array of N. you need log (N) iteration and movement (N / 2) ^ i of the elements on average. so this is an N + log (N) algorithm (which meets your requirement) and has very good practical performance (faster than a simple quick sort, as it avoids any sort, so the output is not ordered).