LeetCode 詳解：Set Matrix Zeroes（矩阵置零）

問題描述

給定一個 m x n 的整數矩陣，若某元素為 0，則將其所在的整行與整列所有元素設為 0。要求 原地修改，空間複雜度最優為 O(1)。

核心思路

第一遍掃描記錄哪些行、哪些列需要置零；第二遍根據記錄執行置零操作。若直接在矩陣上標記會干擾後續判斷，故需額外存儲標記信息。

方法一：兩個布爾數組（O(m+n) 空間）

• row[i] 表示第 i 行含 0
• col[j] 表示第 j 列含 0

掃描矩陣建立標記，再遍歷執行置零。時間 O(mn)，空間 O(m+n)，實現簡單直觀。

方法二：利用矩陣首行首列作為標記（O(1) 空間）

1. 先檢查首行、首列本身是否含 0，記為 firstRowZero, firstColZero。
2. 掃描其餘元素 (i,j) (i>0, j>0)，若為 0，則將 matrix[i][0]=0 和 matrix[0][j]=0 作為標記。
3. 根據首行首列標記，將對應行列（除首行首列外）置零。
4. 最後根據 firstRowZero, firstColZero 決定是否將首行、首列置零。

此法達到 O(1) 額外空間，是面試期望的最優解。

參考實現（C++，方法一）

void setZeroes(vector<vector<int>> &matrix) {
    if (matrix.empty()) return;
    int rows = matrix.size(), cols = matrix[0].size();
    vector<bool> row(rows, false), col(cols, false);

    // 第一遍：記錄含 0 的行列
    for (int i = 0; i < rows; ++i)
        for (int j = 0; j < cols; ++j)
            if (matrix[i][j] == 0)
                row[i] = col[j] = true;

    // 第二遍：執行置零
    for (int i = 0; i < rows; ++i)
        if (row[i])
            fill(matrix[i].begin(), matrix[i].end(), 0);

    for (int j = 0; j < cols; ++j)
        if (col[j])
            for (int i = 0; i < rows; ++i)
                matrix[i][j] = 0;
}

關鍵細節與避坑指南

• 原地修改：不可創建新矩陣返回，必須直接修改引用參數。
• 空矩陣判斷：開頭檢查 matrix.empty() 避免訪問越界。
• 布爾數組初始化：預設 false，遇 0 置 true，避免重複掃描。
• O(1) 空間寫法：注意首行首列的標記角色衝突，必須先單獨記錄其原始狀態。

複雜度總結

延伸思考

若矩陣極大且稀疏，可考慮用 unordered_set 記錄非零行列索引，進一步減少第二遍掃描範圍。但對於常規題目約束，上述兩種方法已足夠。