题目链接：73

思路

这道题的核心思想是，将原矩阵中所有为0的位置记录下来，然后再通过记录来更新原矩阵。而本题算法的好坏，主要是体现在 如何记录原矩阵中所有为0的位置。

最直观的想法便是使用map或是其他数据结构来记录，但这样会引入 非O(1) 的额外空间。有没有更好的方法？

我们可以发现，对于矩阵上任意一个位置(i, j)，如果 matrix[i][j] == 0，它带来的影响其实等效于 matrix[i][0] == 0 && matrix[0][j]。从矩阵图上看的话，就像是把矩阵中的一个点分别垂直映射到了第一行和第一列。有了这个思想，我们可以不使用额外的数据结构（注意是不实用额外的数据结构，不是额外的空间）来记录原矩阵中0的位置，而直接将原矩阵的第一行和第一列作为记录者就可以了。

但需要注意的是，由于第一列和第一行本身就可能存在0，后续的更新会导致原本的0和记录的0无法区分，因此我们可以使用两个bool类型的变量来记录第一行和第一列是否原生含有0。

为什么要专门对第一列、第一行的原生0就行区分呢？因为第一行、第一列的原生0决定了第一行和第一列是否全部都要变成0。如果只有记录0，那么只需要相应位置为0就行了，其他位置可以不变；而如果存在原生0，则除了记录0外，其他位置也全要变成0。由于我们并不关心原生0的具体位置，只需要知道它存不存在，因此使用一个bool类型的变量来存储就行了。

这样空间复杂度只需要 O(1)就行了。

// traverse the matrix and record the position of 0, then update the matrix
// if m[i][j] == 0, it is the same that m[i][0] == 0 && m[0][j] == 0.
// so we map (i, j) to (i, 0) & (0, j)
// but we should record whether the first row and the first column has 0 originally
func setZeroes(matrix [][]int)  {
    hasRow0, hasCol0 := false, false
    // init hasRow0, hasCol0
    for i := range matrix[0] {
        if matrix[0][i] == 0 {
            hasRow0 = true
            break
        }
    }
    for i := range matrix {
        if matrix[i][0] == 0 {
            hasCol0 = true
            break
        }
    }
    // traverse the matrix and map
    for i := 1; i < len(matrix); i++ {
        for j := 1; j < len(matrix[0]); j++ {
            if matrix[i][j] == 0 {
                // map
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }

    // update matrix from right-bottom to left-head
    for i := len(matrix) - 1; i >= 0; i-- {
        for j := len(matrix[i]) - 1; j >= 0; j-- {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
    // if has origin 0 in first row
    if hasRow0 {
        for i := range matrix[0] {
            matrix[0][i] = 0
        }
    }
    // if has origin 0 in first column
    if hasCol0 {
        for i := range matrix {
            matrix[i][0] = 0
        }
    }
}

时间复杂度：O(mn)
空间复杂度：O(1)