1337. The K Weakest Rows in a Matrix
Easy
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.
紀錄有 0~len(mat[0]) 位士兵的有哪幾列,接著從 0 開始遍歷取出前 k 虛弱的列。
func kWeakestRows(mat [][]int, k int) []int {
count := make([][]int, len(mat[0])+1)
for i := 0; i <= len(mat[0]); i++ {
count[i] = []int{}
}
for i := 0; i < len(mat); i++ {
n := 0
for j:=0; j<len(mat[0]); j++ {
if mat[i][j] == 1 { n++ }
}
count[n] = append(count[n], i)
}
res := []int{}
for _, n := range count {
for i:=0; i<len(n); i++ {
res = append(res, n[i])
if len(res) == k {
return res
}
}
}
return res
}