力扣算法题—073矩阵置零

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

示例 1:

输入: 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
输出: 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

示例 2:

输入: 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
输出: 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

进阶:

一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？

 1 #include "_000库函数.h"  2  3  4 //先使用m*n的额外空间  5 class Solution {  6 public:  7 void setZeroes(vector<vector<int>>& matrix) {  8 vector<vector<int>>temp = matrix;  9 for (int i = 0; i < matrix.size(); ++i) 10 for (int j = 0; j < matrix[0].size(); ++j) 11 if (temp[i][j] == 0) { 12 for (int t = 0; t < matrix.size(); ++t) 13 matrix[t][j] = 0; 14 for (int t = 0; t < matrix[0].size(); ++t) 15 matrix[i][t] = 0; 16  } 17  } 18 }; 19 20 //使用m+n的额外空间，只需要记录的行和列就行 21 //此处可以再优化一下，不另外开辟空间，使用原矩阵的第一行和第一列来记录就行 22 class Solution { 23 public: 24 void setZeroes(vector<vector<int>>& matrix) { 25 vector<int>r(matrix.size(), 0);//行标记 m 26 vector<int>l(matrix[0].size(), 0);//列标记 n 27 for (int i = 0; i < matrix.size(); ++i) 28 for (int j = 0; j < matrix[0].size(); ++j) 29 if (matrix[i][j] == 0) { 30 r[i] = 1; 31 l[j] = 1; 32  } 33 34 for (int i = 0; i < matrix.size(); ++i) 35 if (r[i]) 36 for (int j = 0; j < matrix[0].size(); ++j) 37 matrix[i][j] = 0; 38 39 for (int j = 0; j < matrix[0].size(); ++j) 40 if (l[j]) 41 for (int i = 0; i < matrix.size(); ++i) 42 matrix[i][j] = 0; 43  } 44 45 }; 46 void T073() { 47  Solution s; 48 vector<vector<int>>v; 49 v = { { 1,1,1}, { 1,0,1},{ 1,1,1} }; 50  s.setZeroes(v); 51 for (auto &a : v) { 52 for (auto b : a) 53 cout << b << " "; 54 cout << endl; 55  } 56 cout << endl; 57 v = { { 0,1,2,0}, { 3,4,5,2},{ 1,3,1,5} }; 58  s.setZeroes(v); 59 for (auto &a : v) { 60 for (auto b : a) 61 cout << b << " "; 62 cout << endl; 63  } 64 cout << endl; 65 66 67 }