73. Set Matrix Zeroes

Medium

Description

給定一個 m x n 的矩陣，如果某個元素為 0，則將其所在的整行和整列都設為 0。要求原地操作。

Example:

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

Intuition#

核心思路：用矩陣的第一行和第一列作為標記，記錄哪些行列需要歸零，達到 O(1) 額外空間。

不能邊遍歷邊歸零，否則新產生的 0 會造成連鎖反應
需要先記錄哪些行列有 0，再統一歸零
用額外的 Set 記錄需要 O(m + n) 空間；用矩陣自身的第一行/列當標記只需 O(1)

Approaches#

1: 用 Set 記錄#

概念: 先遍歷矩陣找出所有 0 的行列，存入兩個 Set，再遍歷矩陣歸零
時間複雜度: O(m * n) - 遍歷矩陣兩次
空間複雜度: O(m + n) - 兩個 Set 記錄行列

class Solution {
    fun setZeroes(matrix: Array<IntArray>) {
        val rows = HashSet<Int>()
        val cols = HashSet<Int>()
        val m = matrix.size
        val n = matrix[0].size

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (matrix[i][j] == 0) {
                    rows.add(i)
                    cols.add(j)
                }
            }
        }

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (i in rows || j in cols) {
                    matrix[i][j] = 0
                }
            }
        }
    }
}

⭐2: 用第一行/列當標記#

概念: 用第一行和第一列記錄該列/行是否需要歸零，額外用一個變數記錄第一列本身是否需要歸零
時間複雜度: O(m * n) - 遍歷矩陣兩次
空間複雜度: O(1) - 只用一個額外變數

class Solution {
    fun setZeroes(matrix: Array<IntArray>) {
        val m = matrix.size
        val n = matrix[0].size
        var firstColZero = false

        for (i in 0 until m) {
            if (matrix[i][0] == 0) firstColZero = true
            for (j in 1 until n) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0
                    matrix[0][j] = 0
                }
            }
        }

        // 從下往上歸零（避免先改到第一行/列的標記）
        for (i in m - 1 downTo 0) {
            for (j in n - 1 downTo 1) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0
                }
            }
            if (firstColZero) matrix[i][0] = 0
        }
    }
}

歸零時必須從最後一行開始往上處理，因為第一行的標記值在處理其他行時還需要使用。如果先處理第一行，標記會被破壞。

🔑 Takeaways#

Pattern: 利用矩陣自身空間做標記是常見的 O(1) 空間優化技巧
關鍵技巧: 用第一行/列當標記時，處理順序很重要——必須最後才處理用來當標記的那行/列