Обнуление строк и столбцов в массиве

Опубликовано Sep 30, 2011 в Массивы и строки | 1 коммент.


Напишите метод, который бы обрабатывал двумерный массив m*n типа int по следующему принципу: для всех нулевых значений необходимо заполнить нулями все столбцы и строки, которые их содержат.

1 Цель задания быстрая проверка простых навыков алгоритмического мышления
2 Время выполнения 10 минут
3 Формат выполнения код пишется на листике, без доступа к документации

Критерии оценки FulcrumWeb:

Кандидат должен продемонстрировать умение реализовывать элементарные алгоритмы и заботу об эффективности реализации.

Ожидаемые вопросы:

  1. Нужно ли сохранять исходную матрицу?
  2. Насколько много нулей содержит исходная матрица? Велика ли вероятность встретить в ней полностью нулевой столбец или строку?

Оценка результатов:

Первый вопрос должен быть задан. От ответа на него зависит сигнатура метода, необходимость выделения дополнительной памяти и способы реализации. Если старую матрицу нужно сохранить, то память для новой матрицы, разумеется, должна быть выделена. При этом ликвидируется проблема распознавания исходного нуля и полученного после обнуления строки или столбца. Если же исходную матрицу не нужно сохранять, то становится возможным решение без выделения даже временной памяти размера m*n под всю матрицу и его желательно найти.

По поводу второго вопроса. Ясно, что если в исходной матрице имеется строка или столбец, состоящие только из нулей, и этот факт обнаружен, то можно смело прекращать дальнейшее сканирование исходной матрицы, так как результирующая будет состоять целиком из нулей. Тогда, если нужна новая матрица, то ее достаточно просто создать и проинициализировать нулями.