在O(n)时间内找到数组中最大的10个整数

Let S be a set of n integers stored in an array (not necessarily sorted). Design an algorithm to find the 10 largest integers in S (by creating a separate array of length 10 storing those integers). Your algorithm must finish in O(n) time.

假设S是存储在数组中的n个整数(不一定是排序的)。设计一个算法来查找S中最大的10个整数(通过创建一个长度为10的独立数组来存储这些整数)。你的算法必须在O(n)时间内完成。

I thought I could maybe answer this by using count sort and then adding last 10 elements into the new array. But apparently this is wrong. Does anyone know a better way?

我想我可以用count sort来回答这个问题然后在新的数组中加入最后10个元素。但显然这是错误的。有人知道更好的方法吗?

4 个解决方案

#1

Method 1: you can use FindMax() algorithm that find the max number in O(N) and if you use it 10 time :

方法1:可以使用FindMax()算法找到O(N)中的最大值，如果使用10次:

10 * O(N) =O(N)

each time you find max num you put it in the new array and you will ignore it the next time you use FindMax();

每次找到max num时都把它放到新数组中下次使用FindMax()时就会忽略它;

Method 2:

方法2:

you can use Bubble 10 times:

你可以使用10次Bubble:

1) Modify Bubble Sort to run the outer loop at most 10 times.
2) Save the last 10 elements of the array obtained in step 1 to the new array.

10 * O(N) =O(N)

Method 3:

方法3:

You can use MAX Heap:

可以使用MAX Heap:

1) Build a Max Heap in O(n)
2) Use Extract Max 10 times to get 10 maximum elements from the Max Heap 10
* O(logn)

 O(N) + 10 * O(logN) = O(N)

#2

Use order statistic algorithm to find the 10th biggest element. Next, iterate over the array to find all elements which are lesser/equal it.

利用序统计算法求出第10大元素。接下来，遍历数组以查找所有元素，这些元素都小于或等于它。

TimeComplexity: O(n) for order statistic + O(n) for iterating the array once => O(n)

时间复杂度:O(n)用于迭代数组的顺序统计量+ O(n) => O(n)

#3

Visit :

访问:

http://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/

They have mentioned six methods for this.

他们已经提到了六种方法。

#4

-1

Insert them in a balanced binary tree. O(N) + O(lg2 N).

将它们插入到平衡的二叉树中。O(N)+ O(lg2 N)。

#1