🔥个人主页：Milestone-里程碑

❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>

       <<Git>><<MySQL>>

🌟心向往之行必能至

一、题目回顾

给定一个 m x n 的矩阵，若某个元素 matrix[i][j] = 0，则将第 i 行、第 j 列的所有元素置为 0，要求使用原地算法（不能额外开 O (mn) 空间，最多 O (1) 额外空间）。

示例：

• 输入：[[1,1,1],[1,0,1],[1,1,1]]
• 输出：[[1,0,1],[0,0,0],[1,0,1]]

二、踩坑预警：暴力解法为什么不行？

如果直接遍历矩阵，遇到 0 就立刻把所在行 / 列置 0，会出现致命问题：

后面遍历到的 0，可能是自己刚改出来的，并非原始矩阵中的 0，会导致过度置零，最终整个矩阵全变成 0。

比如原始矩阵只有一个 0，暴力修改后会把该行该列都置 0，后续遍历这些新 0 时又会继续扩散，结果完全不符合题意。

三、核心思路：用矩阵首行首列当「标记位」

原地算法的关键是复用矩阵本身空间存储标记，避免额外开数组记录哪些行 / 列需要置零：

1. 标记逻辑

• 用第 0 行标记「哪些列需要置零」
• 用第 0 列标记「哪些行需要置零」
• 额外用两个布尔变量 row0、col0 记录第 0 行本身和第 0 列本身是否需要置零（因为首行首列被用来标记，无法同时存储自己的状态）

2. 步骤拆解

1. 预处理标记：
   • 遍历矩阵，检查是否有 0 出现在第 0 行 / 第 0 列，记录到 row0、col0
   • 遍历 [1, m-1] 行、[1, n-1] 列的元素：若 matrix[i][j] = 0，则将 matrix[i][0] = 0（标记第 i 行）、matrix[0][j] = 0（标记第 j 列）
2. 批量置零：
   • 遍历 [1, m-1] 行：若 matrix[i][0] = 0，则整行置 0
   • 遍历 [1, n-1] 列：若 matrix[0][j] = 0，则整列置 0
3. 处理首行首列：
   • 若 row0 = true，将第 0 行整行置 0
   • 若 col0 = true，将第 0 列整列置 0

四、C++ 代码实现

cpp

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

        // 1. 记录首行、首列是否需要置零
        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;
            }
        }

        // 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 = 0; j < n; ++j) {
                    matrix[i][j] = 0;
                }
            }
        }
        for (int j = 1; j < n; ++j) {
            if (matrix[0][j] == 0) {
                for (int i = 0; i < m; ++i) {
                    matrix[i][j] = 0;
                }
            }
        }

        // 4. 最后处理首行、首列
        if (row0) {
            for (int j = 0; j < n; ++j) {
                matrix[0][j] = 0;
            }
        }
        if (col0) {
            for (int i = 0; i < m; ++i) {
                matrix[i][0] = 0;
            }
        }
    }
};

五、复杂度分析

• 时间复杂度：O (m×n)，遍历矩阵 4 次，属于线性时间
• 空间复杂度：O (1)，仅用了两个布尔变量，完全符合原地算法要求

六、思路总结

这道题的核心是 **「空间复用」思维 **：

• 避免额外数组，用矩阵本身的首行首列存储状态
• 先标记、后修改，避免遍历过程中干扰原始数据
• 最后单独处理首行首列，解决「标记位和自身状态冲突」的问题

这种思路在很多原

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/L070117/article/details/158585747