题目大意：
矩阵置零
给定一个 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] ]
进阶:
- 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗？
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=73
解题思路分析：
题目在进阶中给出了三种解决方案，我们一一来分析一下。
解法一，使用 O(mn) 的额外空间，这种做法比较直接并简单，我们利用原数组copy出一个新数组，遍历新数组中每一个元素，如果是0，则在原数组将该位置对应的行和列都置换为0即可。代码简单，时间复杂度为m*n，空间复杂度也是m*n。
解法二，使用 O(m + n) 的额外空间，我们建立2个boolean型数组，一个代表行，一个代表列。遍历数组中每一个元素，如果是0，表示当前行上存在0，并且当前列上存在0，更新两个boolean数组相对应的行和列，将值更新为true。最后再分别循环一遍2个boolean数组，查看哪些行和列上存在0，就将这些行和列都置换为0。本解法时间复杂度是 m*n，空间复杂度是m+n。
解法三，使用常数级别空间。所谓常数空间就是不能定义数组，只能定义一些基本类型的变量。解题思路其实与解法二类似，只不过我们不需要定义2个boolean型数组。实现上依旧先循环一遍数组中每个元素，如果当前元素是0，那么我们将该元素所在行和列的首元素更改为0，代表改行和列上存在数字0。然后我们再遍历一遍数组，如果该行或者列上的首元素是0，那么我们就将当前元素置换为0。这里需要注意一点，本次循环我们要从行和列下标为1的位置开始循环，如果从0开始循环，可能会将首行或者首列都置换成0，这样会影响接下来的判断。因此本次循环完之后，我们还需要再分别判断一下原数组首行和首列是否包含0，再决定是否将首行和首列都置换为0。本解法时间复杂度是 m*n，空间复杂度是1。
实现代码：
public void setZeroes(int[][] matrix) {
// 首行是否包含0
boolean firstRowHasZero = false;
// 首列是否包含0
boolean firstColHasZero = false;
// 遍历每一个元素
for(int r=0;r<matrix.length;r++){
for(int c=0;c<matrix[0].length;c++){
// 如果当前元素为0
if(matrix[r][c]==0){
// 如果当前是首行，则首行包含0
if(r==0) firstRowHasZero=true;
// 如果当前是首列，首列包含0
if(c==0) firstColHasZero=true;
// 将当前元素所在列的首元素置换为0
matrix[r][0]=0;
// 将当前元素所在行的首元素置换为0
matrix[0][c]=0;
}
}
}
// 循环除去首行和首列的每一个元素
for(int r=1;r<matrix.length;r++){
for(int c=1;c<matrix[0].length;c++){
// 如果当前元素所在行或者所在列包含0，当前元素置换为0
if(matrix[r][0]==0||matrix[0][c]==0){
matrix[r][c]=0;
}
}
}
// 如果首列包含0，将首列置换为0
if(firstColHasZero){
for(int r=0;r<matrix.length;r++){
matrix[r][0]=0;
}
}
// 如果首行包含0，将首行置换为0
if(firstRowHasZero){
for(int c=0;c<matrix[0].length;c++){
matrix[0][c]=0;
}
}
} 本题解法执行时间为2ms。
Runtime: 2 ms, faster than 40.19% of Java online submissions for Set Matrix Zeroes.
Memory Usage: 68.5 MB, less than 5.71% of Java online submissions for Set Matrix Zeroes.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-73-set-matrix-zeroes-解题思路分析/