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

我有一个数字列表，我需要找到其中最小的n个。寻找数组中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;

来源

2014-07-26 Nick Brunt

如果你愿意跑n次以上所有元素foreach循环，就可以避免排序，是的。 – MightyPork

我建议您查看JavaScript本地库。如：https：//developer.mozilla。org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Math/min – mvidaurre

这是一个标准问题，称为分区，但由于某种原因，维基百科称之为[Quickselect]（http://en.wikipedia.org /维基/ Quickselect）。一旦找到第n个最小的数字，分区算法会将所有（n-1）个较小的数字放在其左边。请注意，这些数字本身不会被排序。 –

Array.min = function(array){ 
    return Math.min.apply(Math, array); 
};

来源：http://ejohn.org/blog/fast-javascript-maxmin/

感谢您的澄清。对于n元素使用：

Array.min = function(array, n){ 
    return array.sort(function(a, b){return a-b}).slice(0, n); 
};

来源

2014-07-26 14:42:47 mvidaurre

当然，这只会给我1个号码？我想要最小的'n'数字。 –

经过http://repl.it/languages/JavaScript测试 – mvidaurre

原生Chrome浏览器JavaScript。（Math），数组（array），数组，数组， ..}; => [功能] Array.min（[56,34,27,4,78,12,89,1002,45,33,87,90]） => 4 – mvidaurre

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

从数组中形成一个最小堆。
取出最小元素和heapify。（这一步你会重复，这取决于你有多少项目要）

排序算法需要O（N * logN）的时间，而Min Heap创建（步骤1）将花费O（N）时间，O（logN）{average}将在第二步中耗费时间。

请注意：当您需要的项目数少于N时，堆是非常有用的。如果您重复第2步N次，那么总时间与排序相同即为O（N * logN）本身。

来源

2014-07-26 14:43:20 Dude

没有排序它可以用这种方法完成。基本上这个想法是，每次迭代中的每一次我们都会推送一个数组中的最小数字。和将从主数组中删除该数字

假设我们有长度12

a=[-11,2,1,5,0,9,-8,6,-10,0,12,4];

的阵列，并且我们必须找到4最小数目

我们可以发现使用此功能（AM是结果数组）

function findmin(a) { 
    var item=Math.min.apply(Math, a); 
    var index= a.indexOf(item); 
    am.push(item); 
    a.splice(index, 1); 
    if(am.length<n) 
    findmin(a) 

}

现在假设我们有找到从阵列 9最小的数，我们可以找到（12-9 = 3 ）最大数并将其从给定数组中移除，然后这将是我们的结果。

function findmax(a) { 
    var item=Math.max.apply(Math, a); 
    var index= a.indexOf(item); 
    am.push(item); 
    a.splice(index, 1); 
    if(a.length>n) 
    findmax(a) 

}

这里我认为复杂度是nm，其中m是否定的。元素被发现，n是总数。的元素。如果我没有错。事实上，我很难找到复杂性。所以请建议是否有任何改进可以完成。

SEE DEMO HERE

来源

2014-07-27 07:47:25 Roshan

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

回答

相关问题