Leetcode:73. 矩阵置零

给定一个 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]
]

解题思路：

遍历法，得到所有0的位置，然后记录出现过的行和列，用hash的话可以节省一点内存。对于出现过的行和列，全部置0。

Leetcode:73. 矩阵置零

C++代码
class Solution{ public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(), n = matrix[0].size(); int i, j; for (i = 1; i <= m; i++) { for (j = 1; j <= n; j++) { if (matrix[i - 1][j - 1] == 0) { x[i] = 1; y[j] = 1; } } } unordered_map<int, int>::iterator it; for (it = x.begin(); it != x.end(); it++) { matrix[it->first - 1] = vector<int>(n, 0); } for (it = y.begin(); it != y.end(); it++) { for (i = 1; i <= m; i++) { matrix[i - 1][it->first - 1] = 0; } } } private: unordered_map<int, int> x; unordered_map<int, int> y; };