Set Matrix Zeroes

Средняя№73пометки по краям

Дана матрица чисел. Везде, где стоит 0, нужно обнулить всю его строку и весь его столбец. Менять матрицу на месте, а обнулять строки и столбцы, в которых ноль был с самого начала, а не те, где нули появились по ходу. Наш пример: [5, 2, 7, 1], [3, 0, 4, 6], [0, 8, 9, 2], [7, 1, 3, 5] → [0, 0, 7, 1], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 3, 5].

73 Set Matrix ZeroesРазбор · 1×

Пример: [5, 2, 7, 1], [3, 0, 4, 6], [0, 8, 9, 2], [7, 1, 3, 5]. В строку 0 попадает пометка столбца 1, но своего нуля в ней не было, поэтому 7 и 1 должны остаться.

012301235271304608927135
не менялоськлетку проверяем сейчаспометка: 0 в строке 0 или столбце 0обнулиличисло осталось

Строка 0 — [5, 2, 7, 1]: нуля нет, rowZero = false. В строку 0 и столбец 0 сейчас пойдут пометки, поэтому сначала запоминаем, надо ли обнулять их самих

01/34
сначала · назад · пуск · шаг
Скорость
1function setZeroes(m):
2 rowZero = row 0 has a 0
3 colZero = column 0 has a 0
4 for each (r, c) with r >= 1 and c >= 1:
5 if m[r][c] == 0:
6 m[r][0] = 0; m[0][c] = 0 // the marks
7 for each (r, c) with r >= 1 and c >= 1:
8 if m[r][0] == 0 or m[0][c] == 0:
9 m[r][c] = 0
10 if rowZero:
11 set row 0 to 0
12 if colZero:
13 set column 0 to 0
14 return m
состояние
rowZero
false
colZero
–
r
–
c
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Если обнулять сразу, нули расползутся: свежий 0 выглядит как исходный и обнулит лишние строки и столбцы. Поэтому первый проход только помечает, а второй обнуляет.
  2. Пометкам нужно место для каждой строки и каждого столбца: в столбце 0 есть клетка в каждой строке, а в строке 0 — в каждом столбце, так что матрица хранит свои пометки без доп. памяти.
  3. Пометка в строке 0 выглядит так же, как её собственный ноль, а m[0][0] пришлось бы служить и строке 0, и столбцу 0. Два флага, снятые до первой пометки, их различают, а строку 0 и столбец 0 обнуляем в конце, когда их пометки уже прочитаны.

Сложность

Время O(строки × столбцы): два прохода по клеткам, плюс дважды строка 0 и столбец 0. Память O(1): пометки живут в самой матрице, и ещё два флага.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.