LeetCode 73 Set Matrix Zeroes：O(1) 空間原地標記技巧

問題描述

給定 m×n 矩陣，若某元素為 0，將其所在行、列全部置 0。要求原地修改，空間復雜度 O(1)。

方法一：額外數組記錄（O(m+n) 空間）

void setZeroes(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<bool> row(m, false), col(n, false);
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (matrix[i][j] == 0) row[i] = col[j] = true;
    for (int i = 0; i < m; ++i)
        if (row[i]) fill(matrix[i].begin(), matrix[i].end(), 0);
    for (int j = 0; j < n; ++j)
        if (col[j]) for (int i = 0; i < m; ++i) matrix[i][j] = 0;
}

方法二：O(1) 空間 - 首行首列作標記位

核心思想：用 matrix[0][j] 標記第 j 列需置零，用 matrix[i][0] 標記第 i 行需置零。但首行首列本身也可能需置零，需額外兩個標記變量。

算法流程

1. 檢查首行、首列是否原本含 0 → `firstRowZero`, `firstColZero`
2. 掃描內部元素 (i≥1, j≥1)，若為 0，標記 `matrix[i][0] = matrix[0][j] = 0`
3. 根據標記置零內部元素
4. 根據 `firstRowZero`/`firstColZero` 處理首行首列

完整代碼

void setZeroes(vector<vector<int>>& 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(1) 要求

複雜度

• 時間：O(mn)，三次完整掃描
• 空間：O(1)，只用兩個 bool 變量

面試延伸問題

1. 若矩陣元素為對象而非基本類型，如何標記？（可用單獨標記矩陣或特殊標記值）
2. 能否只用一個額外變量？（可以，用 matrix[0][0] 共享，但需更仔細處理）
3. 並行化如何做？（按行/塊劃分，需同步首行首列標記）