Начните со строки 1. Идите направо, пока не нажмете первую 1. Затем спуститесь в строку 2, но оставайтесь в том же столбце и повторяйте процесс, пока вы не нажмете 1. Делайте это неоднократно. Строка, в которой вы в последний раз сделали правильный шаг, является вашим ответом.
Это решение O (N + M) (для матрицы NxM или O (N) для квадратной матрицы NxN, как указано в вопросе).
Используя ваш пример:
0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1
Здесь . представляют пройденный путь:
. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .
Это решение работает с неквадратными матрицами, сохраняя эффективность O (N + M) в наихудшем случае для матрицы NxM.
Почему это работает? Гарантия того, что числа будут отсортированы, означает, что каждая строка будет серией 0, а затем последовательностью 1. Таким образом, величина строки эквивалентна тому, как далеко вы можете пройти вправо, прежде чем нажать 1. Поэтому, если строка когда-либо может продвинуть вас дальше, просто следуя 0, то она должна быть длиннее, чем все, что мы обрабатывали ранее.
Код Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
ans, j = 0, 0
for i, row in enumerate(li):
while j < len(row) and row[j] == 0:
j += 1
ans = i
print "Row", ans+1, "".join(map(str, li[ans]))
Существует также более простое решение, из-за ограничений всегда иметь квадратную матрицу NxN и отдельные строки вместе. Вместе они означают, что строка с наименьшим значением будет либо 0 0 ... 0 1, либо 0 0 ... 0 0. Это связано с тем, что в матрице представлено N из N + 1 возможных чисел, поэтому «пропущенное» число равно либо 0 (в этом случае наименьшее представленное значение равно 1), либо другому (наименьшее значение равно 0).
Обладая этим знанием, мы проверяем столбец, второй справа, на 0. Когда мы находим один, мы смотрим вправо, и если в нем содержится еще 0, у нас есть ответ (может быть только одна строка, оканчивающаяся на 0). В противном случае мы продолжаем искать в столбце еще один 0. Если мы не найдем еще 0, первой найденной будет строка, которую мы ищем (может быть только одна строка, заканчивающаяся на 01, и поскольку ни один, заканчивающийся на 00, это самое маленькое).
Код Python:
li = [[0, 1, 1, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
[1, 1, 1, 1]]
for i, row in enumerate(li):
if row[-2] == 0:
ans = i
if row[-1] == 0:
break
print "Row", ans+1, "".join(map(str, li[ans]))
Это решение отвечает на вопрос с наименьшими трудностями в O (N), но обобщение его для обработки неквадратных матриц NxM или нечетных чисел приведет к эффективности в худшем случае O (N ^ 2). Я лично предпочитаю первое решение.