K'th數組中的最小元素

Question

給定一個大小爲n的數組，給出一個使用O（1）空間（不是中位數的中值）的確定性算法（不是快速排序），該算法將找到第K個最小項。

有一些明顯的解決方案，比如在nlogn上對數組進行排序，或者在nk中查找最小k時間，但我確信有更好的方法可以做到這一點。它不一定是班輪（我懷疑它是否可以）。

謝謝你的幫手。

Answer 1

排列（使得沒有額外的空間被浪費）的陣列分成min-heap（can be built in O(n) time），然後執行k提取分鐘操作，每個操作whicih的花費O(log n)時間。所以你完全有O(n + k*log n)時間。 （由於k <= n最壞的情況是O(n log n)）

空間複雜度爲O(1)或者，如果算上，我們已經修改了陣列，O(n);但是任何算法都需要這個數組，因此需要那些數組貢獻的空間。由堆產生的額外空間成本是O(1)。

很明顯，這種方法是正確的：第一個extract-min返回（並從堆中移除）最小的元素;第二個extract-min返回（並從堆中移除）第二小元素; ...;和k -th extract-min返回（並從堆中移除）第k-最小的元素。

如果k比n/2「大得多」，那麼您可以使用最大堆並使用類似方法搜索(n-k)第 - 個最大元素來加快速度。