Выбор ответа Senior Матрицы обновлено
Обнуление строк и столбцов
Вопрос
Если элемент равен 0, нужно обнулить его строку и столбец. Как сделать с O(1) доп. памяти?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Первая строка и первый столбец как флаги. Сначала запоминаем, есть ли нули в первой строке и первом столбце, затем помечаем a[i][0] = 0 и a[0][j] = 0, обнуляем внутреннюю часть по меткам и в конце первую строку и столбец.
Варианты ответа
- Обнулять строку и столбец сразу при обходе
- Сделать копию матрицы и читать нули из неё
- Первая строка и первый столбец как флагиправильный ответ
- Set строк и Set столбцов с нулями
Разбор
Сначала запоминаем, есть ли нули в первой строке и первом столбце, затем помечаем a[i][0] = 0 и a[0][j] = 0, обнуляем внутреннюю часть по меткам и в конце первую строку и столбец. O(m · n) времени, O(1) памяти.
- Сразу обнулять нельзя: новые нули распространятся дальше.
- Копия это O(m · n) памяти.
- Два Set это O(m + n), рабочее, но не O(1).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.