在未排序的整数列表中最优搜索 k 个最小值

我刚刚接受采访时提出了一个问题，我很好奇答案应该是什么。问题本质上是：

假设您有一个包含 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)。

这是快速选择 http://en.wikipedia.org/wiki/Quick_select算法。它基本上是一种快速排序，您只需递归数组的一部分。这是一个简单的 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 的中位数之类的东西。