矩阵——矩阵置零

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

这道题要求原地修改矩阵（不能使用额外的矩阵空间），核心思路是：用矩阵的第一行和第一列作为标记位，记录哪些行/列需要置零：最后统一置零。

解题思路：

1. 标记首行首列是否需要置零：因为首行首列要用来做标记，所以先单独记录它们原本是否有0.
2. 用首行首列标记：遍历矩阵其他元素，若matrix[i][j] = 0，则标记matirx[i][0] = 0(第i行需要置零)、matrix[0]j。
3. 置零非首行首列：根据首行首列的标记，把对应行/列置零。
4. 最后置零首行、首列：根据第一步的标记，处理首行首列。

完整代码实现如下：
#include
#include
using namespace std;

class Solution {
public:
void setZeroes(vector<vector>& matrix) {

    int m = matrix.size();    // 矩阵行数int n = matrix[0].size(); // 矩阵列数bool firstRow = false;   // 标记第一行是否需要置零bool firstCol = false;   // 标记第一列是否需要置零// 1. 检查第一行是否有 0for (int j = 0; j < n; j++) {if (matrix[0][j] == 0) {firstRow = true;break;}}// 2. 检查第一列是否有 0for (int i = 0; i < m; i++) {if (matrix[i][0] == 0) {firstCol = true;break;}}// 3. 用第一行第一列标记需要置零的行和列（遍历除首行首列外的元素）for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (matrix[i][j] == 0) {matrix[i][0] = 0; // 标记第 i 行matrix[0][j] = 0; // 标记第 j 列}}}// 4. 根据标记置零非首行首列的元素for (int i = 1; i < m; i++) {if (matrix[i][0] == 0) { // 第 i 行需要置零for (int j = 1; j < n; j++) {matrix[i][j] = 0;}}}for (int j = 1; j < n; j++) {if (matrix[0][j] == 0) { // 第 j 列需要置零for (int i = 1; i < m; i++) {matrix[i][j] = 0;}}}// 5. 最后置零第一行和第一列if (firstRow) {for (int j = 0; j < n; j++) {matrix[0][j] = 0;}}if (firstCol) {for (int i = 0; i < m; i++) {matrix[i][0] = 0;}}
}

};

// 测试代码
int main() {

vector<vector<int>> matrix = {{1, 1, 1}, {1, 0, 1}, {1, 1, 1}};
Solution sol;
sol.setZeroes(matrix);// 输出结果
for (auto& row : matrix) {for (int num : row) {cout << num << " ";}cout << endl;
}
return 0;

}

代码说明：

1. 空间复杂度：O（1），仅使用了两个bool变量，完全满足原地算法要求。
2. 时间复杂度：O（m×n），遍历矩阵常数次，效率最优。
3. 关键细节：

• 必须先单独标记首行首列，否则会被后续标记覆盖（后续处理非行首列需要是以首行首列为标记位的，会将首行首列的对应位置置零），导致结果错误。
• 先处理非首行首列，最后处理首行首列，避免标记被提前覆盖。（非首行首列是以首行首列的标记来置零的，先处理完首行首列的话会把标记覆盖掉）

总结：先标记首行首列，再标记非首行首列，先处理非首行首列，再处理首行首列