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

链接：1337.矩阵中战斗力最弱的K行
难度：Easy
标签：数组、二分查找、矩阵、排序、堆（优先队列）
简介：给你一个大小为  m * n  的矩阵  mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。请你返回矩阵中战斗力最弱的  k  行的索引，按从最弱到最强排序。

题解 1 - typescript

• 编辑时间：2021-08-01
• 执行用时：108ms
• 内存消耗：42.1MB
• 编程语言：typescript
• 解法介绍：哈希储存+二分查找。

function kWeakestRows(mat: number[][], k: number): number[] {
  return mat
    .map((list, i) => [i, find(list)])
    .map(v => {
      console.log(v);
      return v;
    })
    .sort(([i1, v1], [i2, v2]) => (v1 === v2 ? i1 - i2 : v1 - v2))
    .map(([i]) => i)
    .slice(0, k);
  function find(list: number[]): number {
    let l = 0;
    let r = list.length - 1;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (list[mid] === 0) r = mid;
      else l = mid + 1;
    }
    if (list[l] === 1) return list.length;
    return l;
  }
}

题解 2 - typescript

• 编辑时间：2021-08-01
• 执行用时：76ms
• 内存消耗：39.9MB
• 编程语言：typescript
• 解法介绍：哈希储存。

function kWeakestRows(mat: number[][], k: number): number[] {
  return mat
    .map((list, i) => {
      const ans: [number, number] = [i, 0];
      for (const n of list) {
        if (n === 1) ans[1]++;
        else break;
      }
      return ans;
    })
    .sort(([i1, v1], [i2, v2]) => (v1 === v2 ? i1 - i2 : v1 - v2))
    .map(([i]) => i)
    .slice(0, k);
}