LeetCode hot100——73.矩阵置零

题目

给定一个mxn的矩阵，如果一个元素为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
• -231 <= matrix[i][j] <= 231 - 1

进阶：

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

---

题解

class Solution { public void setZeroes(int[][] matrix) { int m = matrix.length; int n = matrix[0].length; boolean row0 = false; boolean col0 = false; // 判断第一行有没有0 for(int j = 0; j < n; j++){ if(matrix[0][j] == 0){ row0 = true; break; } } // 判断第一列有没有0 for(int i = 0; i < m; i++){ if(matrix[i][0] == 0){ col0 = true; break; } } // 使用第一行第一列做标记，i,j从1开始 for(int i = 1;i < m;i++){ for(int j = 1;j < n;j++){ if(matrix[i][j] == 0){ matrix[i][0] = 0; matrix[0][j] = 0; } } } // 根据标记置零 for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ if(matrix[i][0]==0 || matrix[0][j]==0){ matrix[i][j] = 0; } } } // 处理第一行 if(row0){ for(int j = 0; j < n; j++){ matrix[0][j] = 0; } } // 处理第一列 if(col0){ for(int i = 0; i < m; i++){ matrix[i][0] = 0; } } } }

---

思路

题目要求：遇到 0，把整行整列置 0，不能额外开数组记录哪些行、列要清零，利用矩阵第一行、第一列充当标记数组。

核心思路：

1. 先用两个变量记录第一行、第一列本身是否含有 0
2. 遍历除第一行第一列以外的位置，如果matrix[i][j]==0，就把该行第一个元素、该列第一个元素置为 0 做标记
3. 根据第一行、第一列的标记，把对应行、列全部置 0
4. 最后根据最开始记录的两个变量，处理第一行、第一列