LeetCode题解：矩阵中战斗力最弱的 K 行

爱被打了一巴掌 2022-12-29 09:28 142阅读 0赞

# 矩阵中战斗力最弱的 K 行 #

## 一、题目 ##

给你一个大小为 m \* n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

**示例：**

输入：mat =
    [[1,1,0,0,0],
    [1,1,1,1,0],
    [1,0,0,0,0],
    [1,1,0,0,0],
    [1,1,1,1,1]],
    k = 3
    输出：[2,0,3]

**解释：**

每行中的军人数目：
    行 0 -> 2
    行 1 -> 4
    行 2 -> 1
    行 3 -> 2
    行 4 -> 5
    从最弱到最强对这些行排序后得到 [2,0,3,1,4]

## 二、题解 ##

1.  单独分析每一行，并记录原始下标和目标个数
2.  筛选符合题目的数据并返回

/** * @param {number[][]} mat * @param {number} k * @return {number[]} */
    var kWeakestRows = function(mat, k) { 
      const len = mat.length;
      const arr = [];
      for (let i = 0; i < len; i++) { 
        arr.push({  index: i, count: countS(mat[i]) });
      }
      arr.sort((a, b) => { 
        if (a.count === b.count) return a.index - b.index;
        return a.count - b.count;
      });
      return arr.slice(0, k).map(({  index }) => index);
    };
    // 只有统一单行的时候使用了2分法
    const countS = function(nums) { 
      const len = nums.length;
      let left = 0;
      let right = len - 1;
      if (nums[right] === 1) return len;
      while (left <= right) { 
        const mid = left + ((right - left) >> 1);
        if (nums[mid] === 1) { 
          left = mid + 1;
        } else { 
          right = mid - 1;
        }
      }
      return left;
    };

## 三、写在最后 ##

本文是附加题，可能仅仅借助了二分思想中的一部分，加油！

如果对你有所帮助不妨给本项目的[github 点个 star][github _ star]，这是对我最大的鼓励

**关于我**

*  花名：余光
 *  WX：j565017805
 *  沉迷 JS，水平有限，虚心学习中

**其他沉淀**

*  [前端进阶笔记][Link 1]
 *  [JS 版 LeetCode 题解][JS _ LeetCode]
 *  [CSDN][]

![yuguang-csdn-bottom.gif][]

[github _ star]: https://github.com/webbj97/summary
[Link 1]: https://webbj97.github.io/summary/
[JS _ LeetCode]: https://webbj97.github.io/summary/algorithm/
[CSDN]: https://yuguang.blog.csdn.net/
[yuguang-csdn-bottom.gif]: /images/20221120/2f98f1fbdf0846eabfaf16000d21b539.png