73. 矩阵置零 - 力扣（LeetCode）

给定一个 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
• -231 <= matrix[i][j] <= 231 - 1

没有使用原地算法的版本
class Solution {int x,y;ArrayList<Integer> arrx = new ArrayList();ArrayList<Integer> arry = new ArrayList();public void setZeroes(int[][] matrix) {int row = matrix.length;int col = matrix[0].length;for(int i = 0 ; i < row ; i++) {for(int j = 0 ; j < col ; j++) {if(matrix[i][j] == 0 ) {arrx.add(i);arry.add(j);}}}int len = arrx.size();for(int i = 0 ; i < len ; i++) {x = arrx.get(i);y = arry.get(i);process(matrix,row,col);}}public void process(int[][]matrix,int row,int col) {for(int i = 0 ; i < row ; i++)  matrix[i][y] = 0; for(int i = 0 ; i < col ; i++)  matrix[x][i] = 0;}
}

使用原地算法：
class Solution {int x , y ;public void setZeroes(int[][] matrix) {int row = matrix.length;int col = matrix[0].length;for(int i = 0 ; i < row ; ++i) {for(int j = 0 ; j < col ; ++j) {if(matrix[i][j] == 0 ) {x = i ;y = j ;process(matrix,row,col);}}}for(int i = 0 ; i < row ; ++i) {for(int j = 0; j < col ; ++j) {if(matrix[i][j] == '*')  matrix[i][j] = 0;}}}public void process(int[][]matrix,int row,int col) {for(int i = 0 ; i < row ; i++)  {if(matrix[i][y] != 0)matrix[i][y] = '*'; }for(int i = 0 ; i < col ; i++)  {if(matrix[x][i] != 0)matrix[x][i] = '*';}}
}

 今天也是一道中等题。

        首先可能需要说一下原地算法。原地算法_百度百科 (baidu.com)

        在计算机科学中，一个原地算法（in-place algorithm）是一种使用小的，固定数量的额外之空间来转换资料的算法。当算法执行时，输入的资料通常会被要输出的部分覆盖掉。不是原地算法有时候称为非原地（not-in-place）或不得其所（out-of-place）。

       实际上也就是名称很唬人，实际上就是叫你使用O（1）的空间复杂度来完成解答。

现在进入第一个代码的解析：

        根据题目，就是将一个位置是0的行和列都置0。这里要思考到一个问题，你修改的东西会不会影响到后面的if判断，这个对之后很多题目都可能有帮助。如果你一开始遇到一个位置是0的，就先把行和列都转换了。那么在循环进行到后面位置的时候就会出现原本不是0的位置被判断成为0，出现很多原本不应该转换的被转换。所以博主这里用了两个arraylist来存储每个需要改变的位置，所有需要改的位置都找到之后，再针对arraylist里面的方位进行改变。

第二个代码解析：

        这个代码使用了原地算法，可以发现，除了使用x，y，没有在开辟其他变量。而实际的思路跟第一个代码也是差不多的，可以先使用一个标记在原数组中标记需要改变的位置。在循环玩数组之后，就可以对每个需要改变位置的行列进行处理。

当然也可以去看看题解，题解实际上的思路也差不多。最后一个思路会从矩阵最后开始处理。