思路
暴力
代码
二分优化
代码
二分选择 + 前 K 大

leetcode 1337. 矩阵中战斗力最弱的 K 行

August 01, 2021

思路

暴力

对每行出现的军人数量计算,并对数量进行排序,根据题目要求返回排序结果

空间复杂度: $O(M)$, M 为行数 时间复杂度: $O(M * N)$, M 为行数,N 为列数

代码

/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function (mat, k) {
  let arr = [];
  for (let col of mat) {
    let count = 0;
    for (let row of col) {
      if (row === 0) {
        break;
      }
      count++;
    }
    arr.push(count);
  }

  arr = arr.map((v, i) => ({ v, i }));

  return arr
    .sort((a, b) => a.v - b.v)
    .map((item) => item.i)
    .slice(0, k);
};

二分优化

由题意可得,标兵永远在当前行的前面,因此可以通过二分找到最后一个 1 出现的位置,也就是当前行标兵的数量,这样可以将算法的时间复杂度优化到 $O(m * logn)$

代码

var kWeakestRows = function (mat, k) {
  function find(nums) {
    let start = 0,
      end = nums.length - 1;

    while (start <= end) {
      let mid = Math.floor((start + end) / 2);
      if (nums[mid] === 1) {
        start = mid + 1;
      } else {
        end = mid - 1;
      }
    }

    return start;
  }

  let arr = [];
  for (let col of mat) {
    let count = find(col);
    arr.push(count);
  }

  arr = arr.map((v, i) => ({ v, i }));

  return arr
    .sort((a, b) => a.v - b.v)
    .map((item) => item.i)
    .slice(0, k);
};

二分选择 + 前 K 大

这里要求取前 K 大,所以还可以用上前 K 大的优化思想

  1. 使用一个 K 大的最小堆, 每次获取当前行标兵数时,将标兵数 count 推入当前堆, 时间复杂度 $O(m * logK)$
  2. 快速选择,时间复杂度 $O(N)$

feiker 少年起而行之