【2022-09-30每日一题】面试题 01.08. 零矩阵[Medium]

2022-09-30每日一题：面试题 01.08. 零矩阵

难度：Medium

标签：数组 、 哈希表 、 矩阵

编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入：
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出：
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2：

输入：
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出：
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

方法一：自己思路

func setZeroes(matrix [][]int)  {
    queue := [][]int{}
    // 找到所有为0的坐标
    for i, row := range matrix {
        for j, x := range row {
            if x == 0 {
                queue = append(queue, []int{i, j})
            }
        }
    }
    // 遍历所有为0的坐标，分别处理对应的行和列，这里可能重复处理同一行和同一列，没有去重
    for _, q := range queue {
        i, j := q[0], q[1]
        for k := range matrix[i] {
         	matrix[i][k] = 0
        }
        for k := range matrix {
         	matrix[k][j] = 0
        }
    }
}

复杂度分析

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

方法二：使用两个标记数组

详细思路过程见官方题解，这里只做个人刷题记录，方便后续查询阅读

func setZeroes(matrix [][]int) {
    row, col := make([]bool, len(matrix)), make([]bool, len(matrix[0]))
    for i, r := range matrix {
        for j, x := range r {
            if x == 0 {
                row[i] = true
                col[j] = true
            }
        }
    }
    for i, r := range matrix {
        for j := range r {
            if row[i] || col[j] {
                matrix[i][j] = 0
            }
        }
    }
}

复杂度分析

• 时间复杂度：O(mn)
• 空间复杂度：O(m+n)

方法三：使用两个标记变量

func setZeroes(matrix [][]int) {
    m, n := len(matrix), len(matrix[0])
    row0, col0 := false, false
    // 处理第一行
    for _, x := range matrix[0] {
        if x == 0 {
            row0 = true
            break
        }
    }
    // 处理第一列
    for _, r := range matrix {
        if r[0] == 0 {
            col0 = true
        }
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][j] == 0 {
                matrix[i][0] = 0
                matrix[0][j] = 0
            }
        }
    }
     for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
    }
   // 处理第一行
    if row0 {
        for j := 0; j < n; j++ {
            matrix[0][j] = 0
        }
    }
    // 处理第一列
    if col0 {
        for _, r := range matrix {
            r[0] = 0
        }
    }
}

复杂度分析

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

方法四：使用一个标记变量

// 我们可以对方法二进一步优化，只使用一个标记变量记录第一列是否原本存在 0。
// 这样，第一列的第一个元素即可以标记第一行是否出现 0。
// 但为了防止每一列的第一个元素被提前更新，我们需要从最后一行开始，倒序地处理矩阵元素。
func setZeroes(matrix [][]int) {
    n, m := len(matrix), len(matrix[0])
    col0 := false
    for _, r := range matrix {
        if r[0] == 0 {
            col0 = true
        }
        for j := 1; j < m; j++ {
            if r[j] == 0 {
                r[0] = 0
                matrix[0][j] = 0
            }
        }
    }
    for i := n - 1; i >= 0; i-- {
        for j := 1; j < m; j++ {
            if matrix[i][0] == 0 || matrix[0][j] == 0 {
                matrix[i][j] = 0
            }
        }
        if col0 {
            matrix[i][0] = 0
        }
    }
}

复杂度分析

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

LeetCode题库地址

• https://leetcode.cn/problems/zero-matrix-lcci