LC73 - 矩阵置零

package Matrix

// 时间复杂度: O(n * m), 空间复杂度: O(1)
func setZeroes(matrix [][]int) {
    n, m := len(matrix), len(matrix[0])
    // firstRow: 第一行是否被刷成0, firstCol: 第一列是否被刷成零, intersection: matrix[0][0]是否为0
    firstRow, firstCol, intersection := false, false, false
    // (1) 遍历第一行和第一列，初始化上述三个标记
    for i := 0; i < m; i++ {
        if matrix[0][i] == 0 {
            firstRow = true
        }
    }
    for i := 0; i < n; i++ {
        if matrix[i][0] == 0 {
            firstCol = true
        }
    }
    intersection = firstRow || firstCol
    // (2) 遍历右下角矩阵，更新行列代表元素
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
    // (3) 依据行列代表元素的值，刷新右下角矩阵
    for i := 1; i < n; i++ {
        for j := 1; j < m; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    // (4) 依据上述三个标记，刷新第一行和第一列
    if intersection {
        matrix[0][0] = 0
    }
    if firstRow {
        for i := 0; i < m; i++ {
            matrix[0][i] = 0
        }
    }
    if firstCol {
        for i := 0; i < n; i++ {
            matrix[i][0] = 0
        }
    }
}

比较容易想到的是空间复杂度O(n + m)的算法，就是设置一个行标记数组和列标记数组。而上述空间复杂度O(1)的算法就是将第一行和第一列作为了列标记数组和行标记数组，具体过程见注释。