导出最高10个值的子集数组的最简单方法?

我之前的答案使用了反向索引表,但其中包含一些错误(现在已修复),并且比以下代码更难理解。

这实际上是答案中给出的所有解决方案中最慢的一个——为了获得最佳性能,请查看我的另一个答案。

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 ).我将把它作为一个例子,说明如何对多个需求进行排序。..

这会在它搜索的主数组中运行一次,在结果数组中的适当位置插入项目:

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);
}

对于大型数组,这甚至应该相当快,因为大多数时候内部循环应该只进行一次迭代。

这是使用索引表对我之前的答案进行除错的版本。我做了一点基准测试,对于问题中给出的输入,这个解决方案将比到目前为止在这个线程中建议的任何其他方法都要快:

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('], [') + ']]');

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插入时将每个元素排序到结果中可能会更快。

// 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];
}

计算机科学答案:

问题陈述:给定一个长度为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)个元素。