加载中...
1337-矩阵中战斗力最弱的 K 行(The K Weakest Rows in a Matrix)
发表于:2021-12-03 | 分类: 简单
字数统计: 593 | 阅读时长: 3分钟 | 阅读量:

原文链接: 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 row j.
  • 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)$

更多「二分」内容

题目 题解 难度 推荐指数
4. 寻找两个正序数组的中位数 LeetCode 题解链接 困难 🤩🤩🤩🤩
29. 两数相除 LeetCode 题解链接 中等 🤩🤩🤩
33. 搜索旋转排序数组 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
34. 在排序数组中查找元素的第一个和最后一个位置 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
35. 搜索插入位置 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
74. 搜索二维矩阵 LeetCode 题解链接 中等 🤩🤩🤩🤩
81. 搜索旋转排序数组 II LeetCode 题解链接 中等 🤩🤩🤩🤩
153. 寻找旋转排序数组中的最小值 LeetCode 题解链接 中等 🤩🤩🤩
154. 寻找旋转排序数组中的最小值 II LeetCode 题解链接 困难 🤩🤩🤩
220. 存在重复元素 III LeetCode 题解链接 中等 🤩🤩🤩
274. H 指数 LeetCode 题解链接 中等 🤩🤩🤩
275. H 指数 II LeetCode 题解链接 中等 🤩🤩🤩
278. 第一个错误的版本 LeetCode 题解链接 简单 🤩🤩🤩🤩
354. 俄罗斯套娃信封问题 LeetCode 题解链接 困难 🤩🤩🤩
363. 矩形区域不超过 K 的最大数值和 LeetCode 题解链接 困难 🤩🤩🤩
374. 猜数字大小 LeetCode 题解链接 简单 🤩🤩🤩
778. 水位上升的泳池中游泳 LeetCode 题解链接 困难 🤩🤩🤩
852. 山脉数组的峰顶索引 LeetCode 题解链接 简单 🤩🤩🤩🤩🤩
981. 基于时间的键值存储 LeetCode 题解链接 中等 🤩🤩🤩🤩
1004. 最大连续1的个数 III LeetCode 题解链接 中等 🤩🤩🤩
1011. 在 D 天内送达包裹的能力 LeetCode 题解链接 中等 🤩🤩🤩🤩
1208. 尽可能使字符串相等 LeetCode 题解链接 中等 🤩🤩🤩
1438. 绝对差不超过限制的最长连续子数组 LeetCode 题解链接 中等 🤩🤩🤩
1482. 制作 m 束花所需的最少天数 LeetCode 题解链接 中等 🤩🤩🤩
1707. 与数组中元素的最大异或值 LeetCode 题解链接 困难 🤩🤩🤩
1713. 得到子序列的最少操作次数 LeetCode 题解链接 困难 🤩🤩🤩
1751. 最多可以参加的会议数目 II LeetCode 题解链接 困难 🤩🤩🤩
1818. 绝对差值和 LeetCode 题解链接 中等 🤩🤩🤩🤩🤩
1838. 最高频元素的频数 LeetCode 题解链接 中等 🤩🤩🤩
剑指 Offer 53 - I. 在排序数组中查找数字 I LeetCode 题解链接 简单 🤩🤩🤩🤩🤩

以上 $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%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
上一篇:
1358-包含所有三种字符的子字符串数目(Number of Substrings Containing All Three Characters)
下一篇:
1338-数组大小减半(Reduce Array Size to The Half)
本文目录
本文目录