# 1337. 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.

``````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;
}
};
``````

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

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/solutions/1201679/c-python3-no-heap-no-bs-simple-sort-99-20/

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/solutions/496555/java-best-solution-100-time-space-binary-search-heap/

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation