查找数组中的前 N 个元素

Question

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

我想到的解决方案是 1. 使用快速排序对其进行排序，2. 进入前 10 名。

但是还有更好的选择吗？

原文由 zengr 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

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

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

2. 使用步骤 1 中获得的枢轴获取前 k 个。

原文由 Yin Zhu 发布，翻译遵循 CC BY-SA 2.5 许可协议

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大元素的方法是最好的答案。

原文由 nuaavee 发布，翻译遵循 CC BY-SA 3.0 许可协议