Задача: 73. Set Matrix Zeroes
Сложность: medium

Дана матрица размером m×n, состоящая из целых чисел. Если элемент матрицы равен 0, установите в 0 все элементы его строки и столбца.

Необходимо выполнить это действие на месте, не используя дополнительное пространство для другой матрицы.

Пример:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

👨‍💻 Алгоритм:

1⃣Мы перебираем матрицу и отмечаем первую ячейку строки i и первую ячейку столбца j, если условие в приведенном выше псевдокоде выполняется, т.е. если cell[i][j] == 0.

2⃣Первая ячейка строки и столбца для первой строки и первого столбца совпадают, т.е. cell[0][0]. Поэтому мы используем дополнительную переменную, чтобы узнать, был ли отмечен первый столбец, а cell[0][0] используется для того же для первой строки.

3⃣Теперь мы перебираем исходную матрицу, начиная со второй строки и второго столбца, т.е. с matrix[1][1]. Для каждой ячейки мы проверяем, были ли ранее отмечены строка r или столбец c, проверяя соответствующую первую ячейку строки или первую ячейку столбца. Если любая из них была отмечена, мы устанавливаем значение в ячейке на 0. Обратите внимание, что первая строка и первый столбец служат как row_set и column_set, которые мы использовали в первом подходе. Затем мы проверяем, равна ли cell[0][0] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

function setZeroes(&$matrix) {
    $isCol = false;
    $R = count($matrix);
    $C = count($matrix[0]);

    for ($i = 0; $i < $R; $i++) {
        if ($matrix[$i][0] == 0) {
            $isCol = true;
        }
        for ($j = 1; $j < $C; $j++) {
            if ($matrix[$i][$j] == 0) {
                $matrix[0][$j] = 0;
                $matrix[$i][0] = 0;
            }
        }
    }

    for ($i = 1; $i < $R; $i++) {
        for ($j = 1; $j < $C; $j++) {
            if ($matrix[$i][0] == 0 || $matrix[0][$j] == 0) {
                $matrix[$i][$j] = 0;
            }
        }
    }

    if ($matrix[0][0] == 0) {
        for ($j = 0; $j < $C; $j++) {
            $matrix[0][$j] = 0;
        }
    }

    if ($isCol) {
        for ($i = 0; $i < $R; $i++) {
            $matrix[$i][0] = 0;
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний