如何在O（n）中找到數組中的前m個最小整數？

當陣列具有n的長度和1 < =米< = N^0.5如何在O（n）中找到數組中的前m個最小整數？

我想你可以使用一個選擇算法找到的第m個最小整數（有一個複雜的在http://en.wikipedia.org/wiki/Selection_algorithm稱爲BFPRT那是O （n）），然後用它作爲數據分區來獲得前m個最小整數。

但是，有一個方法來做到這一點使用的數據結構，諸如最小堆？我怎麼知道它是否是O（n）？

2013-04-16 Jae

在我看來，答案嵌入在你的問題 - 根據維基百科，min-max堆可以建立在O（n）時間。一旦你有了，獲得最小的元素應該是非常簡單的。 –

見蟒蛇heapq nsmallest，http://docs.python.org/2/library/heapq.html –

重複：http://stackoverflow.com/questions/5577206/generate-top-k-values HTTP：//計算器.com/questions/4956593/optimal-algorithm-for-returning-top-k-values-from-an-array-of-length-n http://stackoverflow.com/questions/12011350/top-5-elements- in-an-unsorted-array – Thomash

您可以創建在線性時間一分堆。然後，您只需刪除每個刪除的最小元素m次，代價爲log(n)。那是O(n) + m*O(log(n))這是O(n) + O(sqrt(n)*log(n))這是O(n)。

編輯我原來說O(n) + O(sqrt(n)*log(n))是O(sqrt(n)*log(n))這是錯誤的，因爲O(n)實際上是o(sqrt(n)*log(n))這意味着它不是O(sqrt(n)*log(n))

來源

2013-04-16 07:53:24 rliu

他需要至少檢查一次數組中的所有單元格。所以線性是最小的 –

你是對的。我的回答完全錯誤。哈哈 – rliu

你編輯它。 .. –

只需使用基數排序在O（n）的時間排序的數組。

來源

2013-04-16 08:00:41

對於大多數實際用途而言，這是正確的，但值得注意的是基數排序取決於數字的長度。 – rliu

@roliu當然可以。 –

Build_Heap（A）方法可以創建在O（n）的時間從隨機陣列min_heap或max_heap，如果我們創建min_heap然後花費O（1）時間來獲得最小的元素

所以總時間來獲得最小元素是O（n）+）（1）即O（n）

來源

2013-04-21 02:50:05 siddstuff

如何在O（n）中找到數組中的前m個最小整數？

回答

相關問題