How to find average of top half of N numbers?

Given N arbitrary integers, how to find average of top half of these numbers? Is there an O(n) solution? If not is it possible to prove tha开发者_如何学运维t it's not possible?

---

First, find a median of the given array (it takes linear time).

Then, just walk through array and sum up all elements that are greater than the median.

Count how many elements you summed (M). If M < N/2, then it means that several elements that are equal to the median value (namely, N/2 - M) belong to the top half. Add to your sum that many median values. We need this complexity because we don't know how many median elements (there can be several) belong to the top half: if we take them all, we can end up having summed more than N/2 elements.

Now you have the sum of the top half of the array. Divide by N/2, and you're done.

---

This is obviously solvable in linear time, if you can find the median in linear time. And finding a median in linear time is tricky, but possible. See for example the wikipedia article on selection algorithms.

---

You could use a priority queue. Insert the elements into the queue maintaining a count of how many elements you've seen, n . Extract n/2 maximum elements from the queue into an accumulator and calculate the average.

With a well chosen data structure behind the queue, such as a fibonacci heap, this will give you O(n log n) runtime, as insertion is O(1) and extraction is O(log n).

Unfortunately not the O(n) runtime you were looking for, but with the data structure already implemented, this would produce very understandable straightforward code.

---

I would suggest this:

Use Quicksort, select some pivot. This will partition your list into two sublist, one smaller than the pivot, one greater than that. If the size of smaller sublist is <= N/2, calculate the average say a1.
If size == N/2 or size == N/2 -1
you are done immediately.

If not repartition the greater sublist till the total size is N/2.

If size > N/2 partition the smaller sublist.

Repeat all till done.

P.S: you don't need to sort.