在未排序的整數列表中優化搜索k個最小值

Question

我剛剛接受了一個問題的採訪，我很好奇答案應該是什麼。問題在於：

假設您有一個未排序的n個整數列表。你如何找到這個列表中的k個最小值？也就是說，如果你有一個[10,11,24,12,13]的列表並且正在尋找2個最小值，你會得到[10,11]。

我有一個O（n * log（k））解決方案，這是我最好的，但我很好奇其他人想出了什麼。我會避免通過發佈我的解決方案污染人們的大腦，並在一段時間內編輯它。

編輯＃1：例如，像函數： 列表getMinVals（名單& L，INT K）

編輯＃2：它看起來就像是一個選擇算法，所以我會在我的解決方案折騰以及;遍歷列表，並使用優先級隊列來保存最小值。優先級隊列的規格是最大值將在優先級隊列的頂部結束，所以在比較頂部與元素時，頂部會彈出，而較小的元素將被推入。這假定優先隊列具有O（log n）推和O（1）彈出。

Answer 1

這是quickSelect算法。這基本上是一種快速排序，你只需要遞歸數組的一部分。這裏有一個簡單的Python實現，爲了簡潔和易讀性而不是效率。

def quickSelect(data, nLeast) : 
    pivot = data[-1] 
    less = [x for x in data if x <= pivot] 
    greater = [x for x in data if x > pivot] 
    less.append(pivot) 

    if len(less) < nLeast : 
     return less + quickSelect(greater, nLeast - len(less)) 
    elif len(less) == nLeast : 
     return less 
    else : 
     return quickSelect(less, nLeast) 

這將在平均O（N）運行，因爲在每次迭代中，我們希望你由乘法常數減少data大小。結果將不會被排序。最糟糕的情況是O（N^2），但這與快速排序的處理方式基本相同，使用諸如-3的中位數之類的東西。

Answer 2

這通常在算法書籍selection algorithms或「線性選擇」下。這裏是具體的section on min/max k values in a list。它是O（nlog（k））。