javascript - 找到数组中 n 个最小数字的最快方法是什么？

Question

我有一个数字列表，我需要找到其中 n 个最小的。

这是我到目前为止所拥有的，但我确信一定可以做得更快、更干净(也许不必先对整个列表进行排序？):

var list = [56,34,27,4,78,12,89,1002,45,33,87,90];
var results = [];
var sorted_list = list.slice(); // fastest way to duplicate array
sorted_list.sort(function (a, b) { 
    return a - b;
});
for (var i = 0; i < n; i++) {
    // do stuff with sorted_list[i] and list
    // push the result to results
}
return results;

Answer 1

我想如果你使用Min Heap解决这个问题，会更快。我的意思是

1. 从数组形成最小堆。
   

2. 取出最小元素并堆化。(您将重复此步骤，具体取决于您想要的项目数量)
   

排序算法将花费 O(N*logN) 时间，而最小堆创建(步骤 1)将花费 O(N) 时间，O(logN){average} 将是第二步花费的时间。

请注意:当您需要的项目数量小于 N 时，堆很有用。如果您重复步骤 2 N 次，则总时间与排序相同，为 O(N*logN) 。