題目描述

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

三種空間複雜度方案對比

O(1) 空間核心技巧

用 matrix[0][j] 標記第 j 列需置零，matrix[i][0] 標記第 i 行需置零。但第一行第一列本身可能原本有 0，需額外兩個變量記錄：

• zeroRow：第一行原本是否有 0
• zeroCol：第一列原本是否有 0

四步驟算法

1. 掃描首行首列：設置 zeroRow, zeroCol
2. 掃描其餘元素：matrix[i][j]==0 → matrix[i][0]=0, matrix[0][j]=0
3. 根據標記置零內部：i=1..m-1, j=1..n-1，若 matrix[i][0]==0 || matrix[0][j]==0 → matrix[i][j]=0
4. 處理首行首列：根據 zeroRow/zeroCol 決定是否置零第一行/列

完整代碼

class Solution {
public:
    void setZeroes(vector>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        if (m <= 1 && n <= 1) return;

        bool zeroRow = false, zeroCol = false;
        // 步驟 1
        for (int i = 0; i < m; i++) if (matrix[i][0] == 0) { zeroCol = true; break; }
        for (int j = 0; j < n; j++) if (matrix[0][j] == 0) { zeroRow = 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] = 0;
                    matrix[0][j] = 0;
                }
        // 步驟 3
        for (int i = 1; i < m; i++)
            if (matrix[i][0] == 0)
                for (int j = 1; j < n; j++) matrix[i][j] = 0;
        for (int j = 1; j < n; j++)
            if (matrix[0][j] == 0)
                for (int i = 1; i < m; i++) matrix[i][j] = 0;
        // 步驟 4
        if (zeroRow) for (int j = 0; j < n; j++) matrix[0][j] = 0;
        if (zeroCol) for (int i = 0; i < m; i++) matrix[i][0] = 0;
    }
};

關鍵細節

• 順序不能亂：必須先記錄首行首列原始狀態，再用它們做標記，最後根據原始狀態處理首行首列
• break 優化：發現一個 0 即可確定該行/列需置零
• 單行/單列矩陣：邏輯自動兼容（內部循環不執行，直接由 zeroRow/zeroCol 決定）

複雜度

• 時間：O(mn) 三次完整掃描
• 空間：O(1) 僅 2 個布爾變量

1. 上一篇文章： C++ 那些細節：函數指針、成員函數指針、回調機制完整詳解
2. 下一篇文章： LeetCode 筆記：Triangle 三角形最小路徑和動態規劃

關於C++

C++ 多重繼承記憶體模型深度剖析：虛函數表、虛繼承與菱形問題

前言 C++ 為支援多型引入虛函數表 (vtable)，為解

Pentium III SSE 指令集深度解析（一）：架構革新與核心優勢

1. Pentium III 處理器概覽 1999 年 2

C++探索之旅（一·十三）：第一部分知識點檢測測驗題與答案解析

測驗題目與答案 #題目選項答案 1C++之父Birj Tr

POJ 3321 Apple Tree：樹上 DFS 序 + 線段樹/樹狀數組動態維護子樹和

問題描述 樹上 N≤1e5 個節點，初始每節點有 1 個蘋果