查找数组中前 N 个元素

algorithm sorting java

2022-09-01 05:13:28

在无序列表（例如100个）中找到前N个（例如10个）元素的最佳解决方案是什么？

我脑海中出现的解决方案是1。使用快速排序对其进行排序，2。进入前10名。

但是有没有更好的选择呢？

答案 1

时间可以减少到线性时间：

答案 2

如果您正在处理固定长度整数等简单元素，那么只要您可以节省与输入数据大小相同的内存缓冲区，则可以使用存储桶或基数排序在O（n）时间内进行排序，这将是最快的。

虽然有线性时间选择算法，但隐藏常数非常高 - 大约24。这意味着O（nlog n）算法对于少于几百万个元素通常更快。

否则，在一般情况下，当您只能比较2个元素并确定哪个元素更大时，问题最好通过堆数据结构来解决。

假设您需要 n 个项目的前 k 个。所有基于对数据进行完全排序的解决方案都需要O（nlog n）时间，而使用堆只需要O（nlog k）时间 - 只需在前k个元素上构建一个堆，然后继续添加一个元素并删除最大值。这将留下一个包含最小 k 个元素的堆。