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 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/