原文链接: 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
i
is 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.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[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.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[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% |
提交历史
提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
---|