Код Senior Матрицы обновлено
Обнуление строк и столбцов
Условие
Если элемент равен нулю, обнули всю его строку и столбец. Мутируй матрицу на месте, верни её. Дополнительной памяти под матрицу не выделяй.
Примеры
setZeroes([[1, 1, 1], [1, 0, 1], [1, 1, 1]]) // [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
setZeroes([[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]) // [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
setZeroes([[1]]) // [[1]]
Как подойти
Ловушка в том, что обнуление по ходу создаёт ложные нули. Решение с двумя множествами тратит O(m+n). Приём с использованием первой строки и столбца как хранилища меток даёт O(1), ценой отдельной обработки самих этих строки и столбца - и именно их забывают.
Подсказки: 2
- Наивное решение обнуляет по ходу и портит ещё не просмотренные клетки.
- Первую строку и первый столбец можно использовать как метки - но их собственное состояние надо запомнить отдельно.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.