我刚刚接受了一个问题的采访,我很好奇答案应该是什么.问题基本上是:
假设你有一个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.