На первый взгляд задача очень проста – просто пройтись по матрице и для каждого нулевого элемента обнулить соответствующие строку и столбец. Но у такого решения есть один большой недостаток: на очередном шаге мы столкнемся с нулями, которые сами же установили. Невозможно будет понять, установили эти нули мы сами или они присутствовали в матрице изначально. Довольно скоро вся матрица обнулится.

Один из способов – создать вторую матрицу, содержащую флаги исходных нулей. Но тогда потребуется сделать два прохода по матрице,что потребует O(N*M).

Так ли нам нужно O(N*M)? Нет. Так как мы собираемся обнулять строки и столбцы, нет необходимости запоминать значения этих элементов. Пусть ноль находится в ячейке [2][4]. Это означает, что необходимо обнулить строку 2 и столбец 4. А если мы обнуляем эти строку и столбец, то зачем их запоминать?

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

public void setZeros(int[][] matrix) {
    boolean[] row = new boolean[matrix.length];
    boolean[] column = new boolean[matrix[0].length];
    
    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (matrix[i][j] == 0) {
                row[i] = true;
                column[j] = true;
            }
        }
    }

    for (int i = 0; i < matrix.length; i++) {
        for (int j = 0; j < matrix[0].length; j++) {
            if (row[i] || column[j]) {
                matrix[i][j] = 0;
            }
        }
    }
}

Для оптимизации можно использовать вместо булева массива бинарный массив.

_{Разбор взят из книги Гейл Л. Макдауэлл «Cracking the Coding Interview» (есть в переводе).}

Хинт для программистов: если зарегистрируетесь на соревнования Huawei Cup, то бесплатно получите доступ к онлайн-школе для участников. Можно прокачаться по разным навыкам и выиграть призы в самом соревновании.

Перейти к регистрации