javascript - 在任意给定间隔内查找数组中 5 个最大数字的有效方法

Question

我试图以设定的时间间隔找到五个最大的数字，同时也从数组中删除这些值。我需要捕获各自范围内的顶尖候选人。该范围可以改变，我需要查询的号码也可以改变。是否有一个有效且最好优雅的解决方案？我所说的优雅是指一种算法(最好是散列)方法，它可以消除低效的排序或对稀疏和大型数组的性能没有贡献的操作。

var arr = [101, 88, 267, 175, 154, 39, 74, 217, 31, 105, 235, 31, 14, 49, 226, 195, 134, 207, 222, 281,
  262, 112, 133, 115, 0, 53, 128, 103, 88, 145, 238, 13, 204, 199, 100, 247, 292, 157, 141, 286,
  72, 160, 85, 61, 57, 54, 263, 50, 125, 179, 243, 281, 39, 76, 151, 79, 1, 238, 200, 249, 35, 82,
  204, 174, 293, 216, 84, 209, 170, 236, 3, 247, 25, 162, 25, 57, 49, 215, 8, 167, 180, 268,
  204, 257, 134, 151, 191, 81, 77, 106, 85, 128, 52, 136, 46, 185, 229, 116, 145, 253, 258, 222,
  269, 225, 101, 175, 265, 77, 32, 8, 72, 54, 111, 264, 292, 161, 91, 215, 139, 245, 73, 127, 297,
  73, 258, 183, 232, 55, 199, 175, 31, 24, 21, 155, 231, 95, 40, 223, 222, 86, 115, 210, 134, 229,
  211, 54, 294, 153, 52, 165, 168, 125,186, 185, 289, 188, 248, 61, 136, 15, 19, 92, 200, 80, 208,
  195, 241, 85, 288, 279, 119, 247, 208, 11, 80, 111, 29, 292, 222, 289, 70, 11, 209, 25, 267, 233,
  16, 289, 154, 141, 174, 30, 156, 40, 266, 139, 116, 241, 1, 101, 109, 61, 220, 265, 45, 178, 166,
  102, 181, 193, 202, 133, 200, 266, 114, 222, 231, 89, 190, 29, 20, 64, 233, 261,213, 40, 161, 167,
  100, 121, 288, 268, 50, 264, 78, 105, 21, 33, 79, 114, 5, 134, 56, 259, 124, 44, 134, 133, 74, 176,
  65, 68, 34, 56, 2, 287, 63, 167, 299, 59, 290, 241, 104, 75, 76, 116, 225, 297, 208, 136, 265, 290,
  170, 267, 10, 176, 141, 217, 195, 4, 173, 32, 150, 271, 238, 171, 195, 16, 282, 77, 62, 39, 44, 248,
  270, 222, 295, 122, 190, 230];
function maxAtIntervals (intervalLength, select, xs) {
    const comparator = (a, b, _) => a - b;
    const temp = [];
    for (var i = 0; i < xs.length; i += intervalLength) {
        const interval = xs.slice(i, i + intervalLength);
        temp.push(interval.sort(comparator).slice(-select));
    }

    return temp;
}
console.log(maxAtIntervals(20, 5, arr));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 1

我已阅读 @le_m 的评论，但是找到 k 个最大/最小的项或第 k 个最大/最小的项是 O(n) 中的一项复杂任务。最好的实现方式是排序并从数组的开头取出必要的元素。

因此，您可以执行以下操作；

function segmentAndTakeMax(ar,sl,mc) { // array , segment length, max count
  var tempar = Array.from({length: sl});
  return Array.from({length: Math.ceil(ar.length/sl)})
              .map((_,i) => tempar.map((_,j) => arr[i*sl+j])
                                  .sort((a,b) => b-a)
                                  .slice(0,Math.min(arr.length-i*sl,mc)));
}

var arr = Array.from(new Array(203), _ => ~~(Math.random()*100));
console.log(arr);
console.log(segmentAndTakeMax(arr,20,5));

.as-console-wrapper { max-height: 100% !important; top: 0; }

好的，根据OP对V8的性能问题，我已经重新编写了代码以使用.reduce()，它比V8中的.map()快得多。这是修改后的代码。

function segmentAndTakeMax(arr, n, m) {
  var li = arr.length-1;  // last index
  return arr.reduce((r,e,i,a) => i%n ? (r[r.length-1].push(e),                                                    // if i%n != 0 then do these -> push e to last sub array
                                        i == li && (r[r.length-1] = r[r.length-1].sort((a,b) => b-a).slice(0,m)), // short circuit for if i == last index then sort and slice the last sub array
                                        r)                                                                        // return r
                                     : (i && (r[r.length-1] = r[r.length-1].sort((a,b) => b-a).slice(0,m)),       // if i%n == 0 then do these -> short circuit for if i != 0 then sort and slice the last sub array
                                        r.push([e]),                                                              // push [e] (a new sub array) to r 
                                        r), []);                                                                  // return r
}

var arr = Array.from(new Array(203), _ => ~~(Math.random()*100));
console.log(arr);
console.log(segmentAndTakeMax(arr,20,5));

.as-console-wrapper { max-height: 100% !important; top: 0; }