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

我刚刚接受了一个问题的采访,我很好奇答案应该是什么.问题基本上是:

假设你有一个n个整数的未排序列表.如何在此列表中找到k个最小值？也就是说,如果你有[10,11,24,12,13]的列表,并且正在寻找2个最小值,那么你会得到[10,11].

我有一个O(n*log(k))解决方案,这是我最好的,但我很好奇其他人想出了什么.我将通过发布我的解决方案来避免污染人们的大脑,并在一段时间内编辑它.

编辑#1:例如,函数如:list getMinVals(list&l,int k)

编辑#2:看起来它是一个选择算法,所以我也会投入我的解决方案; 迭代列表,并使用优先级队列来保存最小值.优先级队列的规范是最大值最终会在优先级队列的顶部,因此在将顶部与元素进行比较时,顶部将弹出,较小的元素将被推送.这假设优先级队列具有O(log n)推送和O(1)pop.

这是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的中位数.