class Solution {
public:
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
}
};
1337. 矩阵中战斗力最弱的 K 行
给你一个大小为 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.lengthn == mat[i].length2 <= n, m <= 1001 <= k <= mmatrix[i][j] 不是 0 就是 1原站题解
golang 解法, 执行用时: 24 ms, 内存消耗: 4.8 MB, 提交时间: 2021-06-15 17:33:57
func kWeakestRows(mat [][]int, k int) []int {
res := make([]int,len(mat))
for i, row := range mat {
res[i] = countOne(row)*100 + i
}
sort.Ints(res)
for i := 0; i < k; i++{
res[i] = res[i]%100
}
return res[:k]
}
func countOne(nums []int) int {
res := 0
for _, num := range nums {
res += num
}
//返回1的个数
return res
}
golang 解法, 执行用时: 20 ms, 内存消耗: 4.9 MB, 提交时间: 2021-06-15 17:29:08
func kWeakestRows(mat [][]int, k int) []int {
r, c := len(mat), len(mat[0])
row := make([]int, r)
num := make([]int, r)
for i := 0; i < r; i++ {
num[i] = i
for j := 0; j < c; j++ {
if mat[i][j] == 0 {
break
}
row[i] += mat[i][j]
}
}
sort.Slice(num, func(i, j int) bool {
if ( row[num[i]] != row[num[j]] ) {
return row[num[i]] < row[num[j]]
}
return num[i] < num[j]
})
return num[:k]
}