查找数组中的前N个元素

Question

在无序列表(例如100)中找到前N个(比如10个)元素的最佳解决方案是什么.

我头脑中的解决方案是1.使用快速排序对其进行排序,2.获得前10名.

但还有更好的选择吗？

Answer 1

时间可以缩短到线性时间:

1. 使用选择算法,可以在线性时间内有效地找到未排序数组中的第k个元素.您可以使用快速排序的变体或更强大的算法.

2. 使用步骤1中的pivot获取前k个.

Answer 2

如何将所有内容委托给Java;)

function findTopN(Array list, int n)
{
    Set sortedSet<Integer> = new TreeSet<>(Comparators.naturalOrder());

    // add all elements from list to sortedSet

    // return the first n from sortedSet
}

我并不想说这是最好的方式.我仍然认为尹竺找到第k个最大元素的方法是最好的答案.

Answer 3

如果你正在处理像固定长度整数这样的简单元素,那么你可以省去与输入数据大小相同的内存缓冲区,可以使用存储桶或基数排序在O(n)时间内完成排序,这样就可以了是最快的.

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

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

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