在O（n）時間中發現陣列中的10個最大整數時間

Question

設S是存儲在數組中的一組n個整數（不一定排序）。設計一個算法來查找S中的10個最大整數（通過創建一個單獨的長度爲10的數組來存儲這些整數）。您的算法必須在O（n）時間內完成。

我想我也許可以通過使用計數排序，然後將最後10個元素添加到新數組來回答這個問題。但顯然這是錯誤的。有誰知道更好的方法？

Answer 1

方法1： 你可以使用FindMax（）算法，找到最大數量O(N)，如果你使用它10時間：

10 * O(N) =O(N) 

每次找到最大NUM時候你把它放在新的數組，你會在下一次忽略它使用FindMax();

方法2：

你CA氮利用泡沫10倍：

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) 

方法3：

您可以使用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) 

Answer 2

使用order statistic算法找出第十大元素。 接下來，迭代數組以找到所有小於/等於它的元素。

TimeComplexity：爲O（n），用於順序統計+ O（n）的用於重複陣列一次=>爲O（n）

Answer 3

訪問：用於

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

他們已經提到六個方法這個。

Answer 4

將它們插入平衡二叉樹。 O（N）+ O（1g2N）。