LeetCode 73 Set Matrix Zeroes：常數空間原地修改矩陣

問題描述

給定一個 m×n 矩陣，若某元素為 0，則將其所在行和列所有元素置 0。要求原地修改，且空間複雜度 O(1)。

進階思路演進

O(1) 空間核心算法

1. 先檢查第一行和第一列是否原本含 0，用兩個布爾變量 firstRowZero, firstColZero 記錄。
2. 掃描其餘元素 (i≥1, j≥1)，若 matrix[i][j]==0，則置 matrix[i][0]=0 和 matrix[0][j]=0 作為標記。
3. 再次掃描 (i≥1, j≥1)，若 matrix[i][0]==0 || matrix[0][j]==0 則置 matrix[i][j]=0。
4. 最後根據 firstRowZero, firstColZero 決定是否將第一行、第一列置零。

代碼實現

class Solution {
public:
    void setZeroes(vector>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool firstRowZero = false, firstColZero = false;
        
        // 1. 檢查首行首列
        for (int j = 0; j < n; ++j) if (matrix[0][j] == 0) { firstRowZero = true; break; }
        for (int i = 0; i < m; ++i) if (matrix[i][0] == 0) { firstColZero = true; break; }
        
        // 2. 用首行首列標記內部元素
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                if (matrix[i][j] == 0)
                    matrix[i][0] = matrix[0][j] = 0;
        
        // 3. 根據標記置零內部元素
        for (int i = 1; i < m; ++i)
            for (int j = 1; j < n; ++j)
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
        
        // 4. 處理首行首列
        if (firstRowZero) for (int j = 0; j < n; ++j) matrix[0][j] = 0;
        if (firstColZero) for (int i = 0; i < m; ++i) matrix[i][0] = 0;
    }
};

關鍵點總結

• 原地性：利用矩陣邊界儲存元數據，不額外申請數組。
• 順序關鍵：必須先記錄首行首列原始狀態，再用它們做標記，最後恢復。
• 邊界情況：1×1、1×n、m×1 矩陣均能正確處理。

複雜度

• 時間：O(mn)，三次完整掃描。
• 空間：O(1)，僅常數額外變量。