Сложность: easy
Вам дана бинарная матрица размером m x n mat, состоящая из 1 (представляющих солдат) и 0 (представляющих гражданских лиц). Солдаты расположены перед гражданскими лицами. То есть, все 1 будут расположены слева от всех 0 в каждой строке.
Строка i слабее строки j, если выполнено одно из следующих условий:
Количество солдат в строке i меньше, чем в строке j.
Обе строки имеют одинаковое количество солдат, но i < j.
Верните индексы k самых слабых строк в матрице, упорядоченных от самой слабой к самой сильной.
Пример:
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].
👨💻 Алгоритм:
1⃣Вычислите силу каждой строки матрицы и поместите пары сила/индекс в массив. Для каждой строки подсчитайте количество единиц (солдат) до первой нуля (гражданского), чтобы определить силу строки.
2⃣Отсортируйте массив пар по возрастанию силы, а в случае равенства силы — по возрастанию индекса. Для этого потребуется реализовать компаратор, который сравнивает сначала силу, а затем индекс.
3⃣Извлеките первые k индексов из отсортированного массива и верните их. Эти индексы будут соответствовать k самым слабым строкам в порядке от самой слабой к самой сильной.
😎 Решение:
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m = len(mat)
n = len(mat[0])
pairs = []
for i in range(m):
strength = 0
for j in range(n):
if mat[i][j] == 0:
break
strength += 1
pairs.append((strength, i))
pairs.sort()
indexes = [pairs[i][1] for i in range(k)]
return indexes
Ставь 👍 и забирай 📚 Базу знаний