一尘不染

在数组中查找前N个元素

algorithm

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

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

但是还有更好的选择吗?


阅读 261

收藏
2020-07-28

共1个答案

一尘不染

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

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

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

2020-07-28