尋找數組中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個最小數字的最快方法是什麼？

回答

相關問題