矩阵置零
题目链接：https://leetcode-cn.com/problems/set-matrix-zeroes/
一、问题描述
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？
示例 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
二、问题分析
因为题目限制了算法的空间复杂度，所以只能向办法在原数组上进行操作，通过观察可以发现，如果有个元素为0，那么该元素对应的行和列都会变成0，那么在遍历数组的时候把要转化为0的行和列都记录下来，然后再把这些行和列转化成0就行了。
因为某些行如果被置0，那么最后该行元素一定全为0，那么这一行的元素就不重要了，所以可以利用这行某个元素来记录整行的最终状态。所以选择第一行和第一列作为一个记录数组，用来记录每行的最终状态，这样在最后矩阵置0的时候可以直接利用第一行和第一列。有一个需要注意的地方是，如果第一行或者第一列中有0，那么最后第一行和第一列也要全置0。
三、算法描述
对第一行和第一列进行遍历，如果有0就标记下，然后遍历整个矩阵，当扫描到0元素的时候，修改该元素对应行和列的第一个元素，用于下次遍历时清0。当扫描完成后，对标记进行判断，如果初始矩阵中第一行或第一列有0，就将第一行或第一列置0，最后返回矩阵。
代码
1 class Solution { 2 public void setZeroes(int[][] matrix) { 3 int n = matrix.length;//行数 4 int m = matrix[0].length;//列数 5 boolean flagrow = false;//用于记录第一行是否有0 6 boolean flagcol = false;//用于记录第一列是否有0 7 for(int i=0;i<n;i++){//遍历第一列，如果有0就记录 8 if(matrix[i][0] == 0){ 9 flagcol = true; 10 } 11 } 12 for(int j=0;j<m;j++){//遍历第一行 13 if(matrix[0][j] == 0){ 14 flagrow = true; 15 } 16 } 17 for(int i=0;i<n;i++){//遍历矩阵，记录要置0的行和列 18 for(int j=0;j<m;j++){ 19 if(matrix[i][j] == 0){ 20 matrix[0][j]=0;//修改行 21 matrix[i][0]=0;//修改列 22 } 23 } 24 } 25 for(int i=0;i<n;i++){ 26 if(matrix[i][0] == 0){ 27 for(int j=0;j<m;j++){ 28 matrix[i][j]=0; 29 } 30 } 31 } 32 for(int j=0;j<m;j++){ 33 if(matrix[0][j]==0){ 34 for(int i=0;i<n;i++){ 35 matrix[i][j]=0; 36 } 37 } 38 } 39 if(flagrow){//第一行有0就重置第一行 40 for(int j=0;j<m;j++){ 41 matrix[0][j]=0; 42 } 43 } 44 if(flagcol){//第一列有0就重置第一列 45 for(int i=0;i<n;i++){ 46 matrix[i][0]=0; 47 } 48 } 49 50 } 51 }
原文：https://www.cnblogs.com/zyq79434/p/15046437.html