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

问题描述

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

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

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

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

但是还有更好的选择吗?

But is there any better alternative?

推荐答案

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

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.

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

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

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