javascript - 获取最大数字的大O

Question

最近遇到这个问题:

编写一个函数，它接受一个数组数组(每个数组包含从大到小排序的数字)和一个数字 (n)。返回最大的 n 个数字。

例如:

findLargest([ [10, 5, 3, 1], [9, 8, 7, 6], [11, 2, 1, 0] ], 5)=> [11, 10, 9, 8, 7]

findLargest([ [15, 5, 3, 1], [10, 8, 7, 6]], 3)=> [ 15, 10, 8 ]

在不复制或修改数组的情况下执行此操作(只需从中读取)。优化时间复杂度。

我想到了这个，但对我的解决方案不太满意:

function findLargest(numberArrays, n ) {
  var results = [];
  var pointers = [];

  for (var x = 0; x < numberArrays.length; x++) {
    pointers.push(0);
  }

  while (results.length < n) {
    var subMaxes = [];
    for (var i = 0; i < pointers.length; i++) {
      var point = pointers[i];
      subMaxes.push(numberArrays[i][point]);
    }
    var max = Math.max.apply(null, subMaxes);
    var indexOfMax = subMaxes.indexOf(max);
    pointers[indexOfMax]++;
    results.push(max);  
  }
  return results;
}

我认为它是 O(n^2).... 是否可以在 O(n) 中完成？

Answer 1

这个问题可以形式化(并稍微调整)为，给定一个维度为 n x n 的二维数组，其中每一行都按降序排列，找到最大的 k 个元素

对于最大的 n 元素，时间复杂度将为 O(nlogn)。 k 最大元素的过程解释如下:

• 构建每行第一个元素的最大堆:时间复杂度为 O(n)

• 从堆中取出最大的元素，从取出元素所属的行开始向堆中插入一个元素。时间复杂度为 O(logn)

• 重复提取所需数量的元素。

因此提取最大数的迭代需要 O(logn) 时间，预处理成本为 O(n)。

提取k个元素，上述算法的时间复杂度为O(klogn)