推导最高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）个元素。