核心思想：
用第一行第一列还存储O(N+M)的额外空间。
因为要占用原有信息，所有循环顺序是关键。
/* * @lc app=leetcode id=73 lang=cpp * * [73] Set Matrix Zeroes */ // @lc code=start class Solution { public: // 核心思路，把第一列和第一行单独拎出来，额外处理，并存储标识 void setZeroes(vector<vector<int>>& matrix) { int N = matrix.size(); int M = matrix[0].size(); // 单独处理第一列 bool flag = false; for(int i=0;i<N;i++){ if(matrix[i][0] == 0){ flag = true; break; } } // 更换第一列第一行标识 for(int i=0;i<N;i++){ for(int j=1;j<M;j++){ if(matrix[i][j] == 0){ matrix[i][0] = matrix[0][j] = 0; } } } // 矩阵除第一列，所有元素更新 for(int i=N-1;i>=0;i--){ if(matrix[i][0] == 0){ for(int j=1;j<M;j++) matrix[i][j] = 0; }else{ for(int j=1;j<M;j++){ if(matrix[0][j] == 0){ matrix[i][j] = 0; } } } } // 单独处理第一列 if(flag) for(int i=0;i<N;i++) matrix[i][0] = 0; } }; // @lc code=end