Почему это работает
- Если обнулять сразу, нули расползутся: свежий 0 выглядит как исходный и обнулит лишние строки и столбцы. Поэтому первый проход только помечает, а второй обнуляет.
- Пометкам нужно место для каждой строки и каждого столбца: в столбце 0 есть клетка в каждой строке, а в строке 0 — в каждом столбце, так что матрица хранит свои пометки без доп. памяти.
- Пометка в строке 0 выглядит так же, как её собственный ноль, а m[0][0] пришлось бы служить и строке 0, и столбцу 0. Два флага, снятые до первой пометки, их различают, а строку 0 и столбец 0 обнуляем в конце, когда их пометки уже прочитаны.
Сложность
Время O(строки × столбцы): два прохода по клеткам, плюс дважды строка 0 и столбец 0. Память O(1): пометки живут в самой матрице, и ещё два флага.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗