对未排序整数列表中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 )推送和O(1)弹出。
回答 2
Stack Overflow用户
发布于 2009-02-17 13:16:14
这是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的中位数。
Stack Overflow用户
发布于 2009-02-17 13:17:53
这通常在selection algorithms或“线性选择”下的算法书籍中。下面是具体的section on min/max k values in a list。是O(nlog(k))。
https://stackoverflow.com/questions/558729
复制
相似问题
智能家居操作和DialogFlow操作之间的主要区别
伪操作和机器操作的区别？
Oozie >异步操作和同步操作之间的区别是什么？
Delphi字节操作和Java
增加虚拟字节的操作和函数
领取专属 10元无门槛券
AI混元助手 在线答疑
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
