推導最高10個值的子集數組的最簡單方法？

Question

在JavaScript的我有一個數組如下：

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4]; 

而我感興趣的是找到一種方法（一個循環中，而不是多個）來導出的最高10個值，的一個子集陣列，其中的先前位置值是「鑰匙」（所以模擬Map對象）：

如：

var fooTopTen = [[4, 128], [18, 128], [25, 60], [27, 28], [10, 27], [37, 27], [15, 21], [9, 18], [14, 18], [23, 18]]; 

Answer 1

我以前的答案使用一個反向索引表，但包含一些錯誤 - 現在已經修復 - 比以下代碼更難理解。

這實際上是答案中給出的所有解決方案中最慢的 - 爲獲得最佳性能，請檢查我的其他答案。

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4]; 

var fooTopTen = []; 

// add index to values 
for(var i = 0, len = foo.length; i < len; ++i) 
    fooTopTen.push([i, foo[i]]); 

// sort first by value (descending order), then by index (ascending order) 
fooTopTen.sort(function(t1, t2) { 
    return t2[1] - t1[1] || t1[0] - t2[0]; 
}); 

// shorten array to correct size 
fooTopTen.length = 10; 

// output top ten to check result 
document.writeln('[[' + fooTopTen.join('], [') + ']]'); 

比較功能是不需要的（一個比較所述索引）的第二部分，如sort()是在大多數實現穩定（這不是必須由ECMA according to MDC）。我會離開它作爲一個例子來如何與多種需求可以做排序...

Answer 2

下面是一個使用索引表我以前的答案去bug的版本。我做了一些基準測試，並在題所給的輸入，這個孤子將是比什麼都已經提出的在此線程至今快：

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4]; 

var indexTable = {}, uniqueValues = []; 

// --- build reverse index table, find unique values 

for(var i = foo.length; i--;) { 
    var value = foo[i]; 
    if(indexTable.hasOwnProperty(value)) 
     indexTable[value].push(i); 
    else { 
     indexTable[value] = [i]; 
     uniqueValues.push(value); 
    } 
} 

// --- sort unique values in ascending order 

uniqueValues.sort(function(i1, i2) { 
    return i1 - i2; 
}); 

// --- find ten greatest values 

var fooTopTen = [], k = 0; 

for(var i = uniqueValues.length; k < 10 && i--;) { 
    var value = uniqueValues[i], 
     indices = indexTable[value]; 

    for(var j = indices.length; k < 10 && j--;) 
     fooTopTen[k++] = [indices[j], value]; 
} 

// --- output result 

document.writeln('[[' + fooTopTen.join('], [') + ']]'); 

Answer 3

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4]; 

var index = 0; 
var result = foo.map(function(a){ return [index++, a]; }) 
     .sort(function(a,b){ return (a[1] < b[1]); }) 
     .splice(0, 10); 

document.write(result.join(' ')); 

如果比較結果的要求，它可能會更快大小foo是非常大的遍歷FOO插入當我們遇到它時將每個元素分解成結果。

Answer 4

// Sorting method 
function sortNumber(a, b) { 
    return a - b; 
} 

// Find the offset of an element in array 
function findOffset(element, array) { 
    for (var i = 0; i < array.length; i++) { 
     if (array[i] == element) { 
      // Make sure we don't find it again 
      array[i] = null; 
      return i; 
     } 
    } 
} 

var foo = [2, 2, 4, 4, 128, 2, 2, 1, 4, 18, 27, 16, 2, 1, 18, 21, 5, 1, 128, 1, 2, 2, 1, 18, 12, 60, 2, 28, 1, 17, 2, 3, 4, 2, 2, 2, 1, 27, 2, 17, 7, 2, 2, 2, 5, 1, 2, 4, 7, 1, 2, 1, 1, 1, 2, 1, 5, 7, 2, 7, 6, 1, 7, 1, 5, 8, 4]; 
// Copies 
var bar = foo.slice(); 
var baz = foo.slice(); 
var fooTopTen = new Array(10); 
// Sort 
bar.sort(sortNumber).reverse(); 
// Create the results 
for (var i = 0; i < 10; i++) { 
    fooTopTen[i] = new Array(2); 
    fooTopTen[i][0] = findOffset(bar[i], baz); 
    fooTopTen[i][1] = bar[i]; 
} 

Answer 5

這通過它搜索主陣列運行一次，在結果數組中的適當位置插入項目：

function top10(arr) { 
    var results = [[0,Number.MAX_VALUE],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0],[0,0]]; 

    for (var i=0; i<arr.length; i++) { 
    // search from back to front 
    for (var j=9; j>=0; j--) { 
     if (arr[i] <= results[j][1]) { 
     if (j==9) 
      break; 
     results.splice(j+1, 0, [i, arr[i]]); 
     results.pop(); 
     break; 
     } 
    } 
    } 
    return results.slice(1); 
} 

對於大型陣列，這甚至應該是相當快的，因爲大部分時間內循環只應該做一次迭代。

Answer 6

計算機科學-γ應答：

問題陳述：給定的長度爲N的大陣列X，和一個小數目m < N（這裏M = 10），產生的長度m，其中每一個列Y Y的元素包含對{i，X [i]}，使得X {i}的集合是X的m個最大元素。如果m比N小得多，則循環X和將它們分類爲Y，丟棄對以維持至多m個元素。 （即提到的月影）

排序X將花費你O（N log N）個元素。迭代X並排序到Y應該只需要O（N log m）個元素。