Начните с правого верхнего угла: на единице двигайтесь влево, на нуле переходите к следующей строке. Максимум в примере у строки с индексом 3; сложность O(строки + столбцы).
Определение строки с наибольшим количеством единиц
Начните с правого верхнего угла: на единице двигайтесь влево, на нуле переходите к следующей строке. Максимум в примере у строки с индексом 3; сложность O(строки + столбцы).
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дана квадратная матрица, содержащая только нули и единицы. В каждой строке после появления первой единицы все последующие элементы также равны единице. Требуется найти индекс строки, в которой количество единиц максимально, используя оптимальный алгоритм.
grid = [
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 1, 1, 1, 1],
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1]
]
Ответ
Начните с правого верхнего угла: на единице двигайтесь влево, на нуле переходите к следующей строке. Максимум в примере у строки с индексом 3; сложность O(строки + столбцы).
Несмотря на слово «квадратная», пример имеет размер 6×5; алгоритм работает и для прямоугольной матрицы:
def most_ones(grid):
if not grid or not grid[0]:
return -1
col = len(grid[0]) - 1
best = 0
for row_index, row in enumerate(grid):
while col >= 0 and row[col] == 1:
best = row_index
col -= 1
return best
Предполагаются одинаковая длина строк и их отсортированность. Указатель столбца никогда не возвращается вправо. При равенстве максимумов остаётся первая строка; для непустой матрицы из нулей возвращается 0.