【LeetCode热题100】73.矩阵置零（矩阵）

一.题目要求

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

二.题目难度

中等

三.输入样例

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示： m == matrix.length n == matrix[0].length 1 <= m, n <= 200 − 2 31 -2^{31} −231 <= matrix[i][j] <= 2 31 − 1 2^{31} - 1 231−1

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

四.解题思路

没什么可说的 官方解法是优化后的

五.代码实现 class Solution { public: void setZeroes(vector<vector<int>>& matrix) { set<int> zeroh,zerol; vector<vector<int>>::iterator it; vector<int>::iterator itt; for (it = matrix.begin(); it != matrix.end(); it++) { for (itt = (*it).begin(); itt != (*it).end(); itt++) { if (*itt == 0) { zeroh.insert(it - matrix.begin()); zerol.insert(itt - (*it).begin()); } } } for (set<int>::iterator it = zeroh.begin(); it != zeroh.end(); it++) { for (vector<int>::iterator itl = matrix[*it].begin(); itl != matrix[*it].end(); itl++) { *itl = 0; } } for (set<int>::iterator it = zerol.begin(); it != zerol.end(); it++) { for (vector<vector<int>>::iterator ith = matrix.begin(); ith != matrix.end(); ith++) { (*ith)[*it] = 0; } } } };

官方给的优化方法

class Solution { public: void setZeroes(vector<vector<int>>& matrix) { bool firstRowZero = false, firstColZero = false; int rows = matrix.size(), cols = matrix[0].size(); // Determine if the first row or first column is all zeros for (int i = 0; i < rows; i++) { if (matrix[i][0] == 0) { firstColZero = true; break; } } for (int j = 0; j < cols; j++) { if (matrix[0][j] == 0) { firstRowZero = true; break; } } // Use first row and column as markers, set matrix[i][0] and matrix[0][j] to 0 if matrix[i][j] is 0 for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { if (matrix[i][j] == 0) { matrix[i][0] = 0; matrix[0][j] = 0; } } } // Zero out cells based on the first row and column for (int i = 1; i < rows; i++) { for (int j = 1; j < cols; j++) { if (matrix[i][0] == 0 || matrix[0][j] == 0) { matrix[i][j] = 0; } } } // Zero out the first row and column if needed if (firstColZero) { for (int i = 0; i < rows; i++) matrix[i][0] = 0; } if (firstRowZero) { for (int j = 0; j < cols; j++) matrix[0][j] = 0; } } }; 六.题目总结

无