原文链接: https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix
英文原文
You are given an m x n binary matrix mat of 1's (representing soldiers) and 0's (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1's will appear to the left of all the 0's in each row.
A row i is weaker than a row j if one of the following is true:
- The number of soldiers in row
iis less than the number of soldiers in rowj. - Both rows have the same number of soldiers and
i < j.
Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.
Example 1:
Input: 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 Output: [2,0,3] Explanation: The number of soldiers in each row is: - Row 0: 2 - Row 1: 4 - Row 2: 1 - Row 3: 2 - Row 4: 5 The rows ordered from weakest to strongest are [2,0,3,1,4].
Example 2:
Input: mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 Output: [0,2] Explanation: The number of soldiers in each row is: - Row 0: 1 - Row 1: 4 - Row 2: 1 - Row 3: 1 The rows ordered from weakest to strongest are [0,2,3,1].
Constraints:
m == mat.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j]is either 0 or 1.
中文题目
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
示例 1：
输入：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]
示例 2：
输入：mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 输出：[0,2] 解释： 每行中的军人数目： 行 0 -> 1 行 1 -> 4 行 2 -> 1 行 3 -> 1 从最弱到最强对这些行排序后得到 [0,2,3,1]
提示：
m == mat.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j]不是 0 就是 1
通过代码
高赞题解
朴素解法
一个朴素的做法是对矩阵进行遍历，统计每一行的军人数量，并以二元组 $(cnt_i, idx_i)$ 的形式进行存储。
然后对所有行的战力进行排序，选出战力最小的 $k$ 个下标即是答案。
代码：
[]class Solution { public int[] kWeakestRows(int[][] mat, int k) { int m = mat.length, n = mat[0].length; int[][] all = new int[m][2]; for (int i = 0; i < m; i++) { int cur = 0; for (int j = 0; j < n; j++) cur += mat[i][j]; all[i] = new int[]{cur, i}; } Arrays.sort(all, (a, b)->{ if (a[0] != b[0]) return a[0] - b[0]; return a[1] - b[1]; }); int[] ans = new int[k]; for (int i = 0; i < k; i++) ans[i] = all[i][1]; return ans; } }
- 时间复杂度：遍历矩阵的复杂度为 $O(m * n)$；排序复杂度为 $O(m\log{m})$；构造答案复杂度为 $O(k)$。整体复杂度为 $O(\max(m * n, m\log{m}))$
- 空间复杂度：$O(m)$ 空间用于存储所有的行战力；$O(\log{m})$ 空间用于排序。整体复杂度为 $O(m + \log{m})$
二分 + 优先队列（堆）
根据「军人总是排在靠前位置」的特性，我们可以通过「二分」找到每一行最后一个军人的位置，从而在 $O(\log{n})$ 的复杂度内统计出每行的军人数量（战力情况）。
同时由于我们只需要「战力最弱」的 $k$ 行数据，这引导我们可以建立一个「战力大根堆」来做，「战力大根堆」存放着数量最多为 $k$ 的战力二元组 $(cnt_i, idx_i)$，堆顶元素为战力最大的数对。
每次通过「二分」得到当前行的战力值后，判断当前战力值与堆顶元素的战力大小关系：
- 如果当前战力值比堆顶的元素要大：直接丢弃当前战力值（不可能属于在第 $k$ 小的集合中）；
- 如果当前战力值比堆顶的元素要小：将堆顶元素弹出，将当前行放入堆中。
一些细节：每次写二分都有同学会问，
check函数怎么写，可以重点看看 34 题题解。由于考虑某行没有军人的情况，我们需要二分完检查一下分割点是否符合check来决定军人数量。
另外，从堆弹出和往堆存入，需要与当前堆元素的数量有所关联。
代码：
[]class Solution { public int[] kWeakestRows(int[][] mat, int k) { int m = mat.length, n = mat[0].length; PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{ if (a[0] != b[0]) return b[0] - a[0]; return b[1] - a[1]; }); for (int i = 0; i < m; i++) { int l = 0, r = n - 1; while (l < r) { int mid = l + r + 1 >> 1; if (mat[i][mid] >= 1) l = mid; else r = mid - 1; } int cur = mat[i][r] >= 1 ? r + 1 : r; if (q.size() == k && q.peek()[0] > cur) q.poll(); if (q.size() < k) q.add(new int[]{cur, i}); } int[] ans = new int[k]; int idx = k - 1; while (!q.isEmpty()) ans[idx--] = q.poll()[1]; return ans; } }
- 时间复杂度：二分得到每行的战力情况，复杂度为 $O(m\log{n})$；堆中最多有 $k$ 个元素，将行信息存入堆中复杂度为 $O(m\log{k})；$构造答案复杂度为 $O(k\log{k})$。整体复杂度为 $O(m * (\log{n} + \log{k}))$
- 空间复杂度：$O(k)$
更多「二分」内容
以上 $Tag$ 分类摘自 wiki
更多「优先队列（堆）」内容
| 题目 | 题解 | 难度 | 推荐指数 |
|---|---|---|---|
| 23. 合并K个升序链表 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 218. 天际线问题 | LeetCode 题解链接 | 困难 | 🤩🤩🤩 |
| 264. 丑数 II | LeetCode 题解链接 | 中等 | 🤩🤩🤩 |
| 451. 根据字符出现频率排序 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 480. 滑动窗口中位数 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 692. 前K个高频单词 | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
| 703. 数据流中的第 K 大元素 | LeetCode 题解链接 | 简单 | 🤩🤩🤩 |
| 726. 原子的数量 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩 |
| 987. 二叉树的垂序遍历 | LeetCode 题解链接 | 困难 | 🤩🤩🤩🤩🤩 |
| 1834. 单线程 CPU | LeetCode 题解链接 | 中等 | 🤩🤩🤩🤩 |
以上 $Tag$ 分类摘自 wiki
最后
如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 39769 | 56409 | 70.5% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
