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 by n 的矩阵,只有0和1两个数字,每行中所有的1是排在0前面的,现在让找出前k个1最少的行,若1的个数相同,则行数坐标小的排前面。由于每行是按照1的个数来排序的,所以需要知道每行中1的个数,题目中说了所有的1是在0的前面,只需要从前往后遍历,遇到第一个0的时候就可以停止遍历了,因为后面的肯定都是0了。这里每行只需要提取出两个信息,一个是1的个数,另一个是该行的坐标,将每行的这两个信息提取出来放到一个数组中,然后对该数组进行排序,需要自定义排序的方式,即按照1的个数从小到大排序,遇到相同的,按照坐标大小排序。这样只要取出排序后前k个行数坐标放到结果 res 中即可,参见代码如下:
解法一:
class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<int> res;
vector<vector<int>> nums;
for (int i = 0; i < mat.size(); ++i) {
int cnt = 0;
for (int j = 0; j < mat[i].size(); ++j) {
if (mat[i][j] == 1) ++cnt;
else break;
}
nums.push_back({i, cnt});
}
sort(nums.begin(), nums.end(), [](vector<int>& a, vector<int>& b){
return (a[1] == b[1]) ? a[0] < b[0] : a[1] < b[1];
});
for (int i = 0; i < k; ++i) {
res.push_back(nums[i][0]);
}
return res;
}
};
再来看一种写法更简洁的解法,这里做个小 trick,即在每行末尾加入一个数字,即该行的坐标。这样做有两个好处,一个是 tie breaker,即打破平局,当两行1个数相同的时候,由于行数坐标的存在,可是使得行数小的排在前面,另一个就是保存行信息,由于该数字的存在,即便是打乱了顺序,也能知道该行的原始行坐标。现在只需要直接给数组进行排序就行就行了,取出前k个的原始行坐标放到结果 res 中即可,参见代码如下:
解法二:
class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<int> res;
for (int i = 0; i < mat.size(); ++i) {
mat[i].push_back(i);
}
sort(mat.begin(), mat.end());
for (int i = 0; i < k; ++i) {
res.push_back(mat[i].back());
}
return res;
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/1337
参考资料:
https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/
LeetCode All in One 题目讲解汇总(持续更新中…)
(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,快快加入吧~)
微信打赏
|
Venmo 打赏
—|—
转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com