在无序列表(例如100个)中找到前N个(例如10个)元素的最佳解决方案是什么?
我想到的解决方案是1.使用快速排序对其进行排序,2.获得前10名。
但是还有更好的选择吗?
时间可以减少为线性时间:
使用选择算法,可以在线性时间内有效地找到未排序数组中的第k个元素。您可以使用快速排序的变体,也可以使用更强大的算法。
使用步骤1中获得的枢轴获取顶部k。