LeetCode 73：矩陣置零——常數空間利用首行首列標記

題目描述

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

O(1) 空間算法

1. 用兩布爾變量 firstRowZero、firstColZero 記錄首行、首列是否原本含 0。
2. 掃描其餘元素 (i>0, j>0)，若 matrix[i][j]==0，標記 matrix[i][0]=0、matrix[0][j]=0。
3. 根據首行首列標記，將內部元素置 0。
4. 最後根據 firstRowZero/firstColZero 處理首行首列。

C++ 實現

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        bool row0 = false, col0 = false;
        for (int j = 0; j < n; ++j) if (matrix[0][j] == 0) { row0 = true; break; }
        for (int i = 0; i < m; ++i) if (matrix[i][0] == 0) { col0 = true; break; }

        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;

        for (int i = 1; i < m; ++i)
            if (matrix[i][0] == 0)
                fill(matrix[i].begin()+1, matrix[i].end(), 0);
        for (int j = 1; j < n; ++j)
            if (matrix[0][j] == 0)
                for (int i = 1; i < m; ++i) matrix[i][j] = 0;

        if (row0) fill(matrix[0].begin(), matrix[0].end(), 0);
        if (col0) for (int i = 0; i < m; ++i) matrix[i][0] = 0;
    }
};

複雜度

• 時間：O(mn) 三次遍歷。
• 空間：O(1) 額外空間。