Description
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.
Solution
Python3
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
res = []
pq = []
for i, row in enumerate(mat):
count = row.count(1)
if len(pq) == k:
heappushpop(pq, (-count, -i))
else:
heappush(pq, (-count, -i))
while pq:
_, i = heappop(pq)
res.append(-i)
res.reverse()
return res
Python
class Solution(object):
def kWeakestRows(self, mat, k):
"""
:type mat: List[List[int]]
:type k: int
:rtype: List[int]
"""
temp = [[sum(mat[i]),i ]for i in range(len(mat))]
lst = sorted(temp)
return ([i[1] for i in lst[:k]])