查找数组中的前N个元素 [英] Find top N elements in an Array

问题描述

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

What would be the best solution to find top N (say 10) elements in an unordered list (of say 100).

用它快速排序，2，得到最高里面传来在我脑海中的解决方案是为1类10

The solution which came in my head was to 1. sort it using quick sort, 2. get top 10.

但有没有更好的选择？

推荐答案

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

The time could be reduced to linear time:

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

1. Use the selection algorithm, which effectively find the k-th element in a un-sorted array in linear time. You can either use a variant of quick sort or more robust algorithms.

获取相关的前k使用了支点在第1步

Get the top k using the pivot got in step 1.

这篇关于查找数组中的前N个元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！