Задача: 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] нулю, если это так, мы отмечаем первую строку как ноль. И, наконец, если первый столбец был отмечен, мы делаем все записи в нем нулевыми.

😎 Решение:

func setZeroes(_ matrix: inout [[Int]]) {
    var isCol = false
    let R = matrix.count
    let C = matrix[0].count
    
    for i in 0..<R {
        if matrix[i][0] == 0 {
            isCol = true
        }
        for j in 1..<C {
            if matrix[i][j] == 0 {
                matrix[0][j] = 0
                matrix[i][0] = 0
            }
        }
    }
    
    for i in 1..<R {
        for j in 1..<C {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    
    if matrix[0][0] == 0 {
        for j in 0..<C {
            matrix[0][j] = 0
        }
    }
    
    if isCol {
        for i in 0..<R {
            matrix[i][0] = 0
        }
    }
}

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