在未排序的整数列表中优化搜索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））。