题目
给定一个 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]
]
思路一
定义两个数组，分别表示第 i 行，第 j 列是否需要置零，遍历数组，得到所有需要置零的行和列，然后将分别将这些行和列置零；空间复杂度
O
(
m
+
n
)
O(m + n)
O(m+n)
代码一
class Solution {
public void setZeroes(int[][] matrix
) {
int m
= matrix
.length
, n
= 0;
if (m
> 0)
n
= matrix
[0].length
;
boolean[] h
= new boolean[m
], v
= new boolean[n
];
for (int i
=0; i
<m
; i
++) {
for (int j
= 0; j
< n
; j
++) {
if (matrix
[i
][j
] == 0){
h
[i
] = v
[j
] = true;
}
}
}
for (int i
=0; i
<m
; i
++){
if (h
[i
]){
for (int j
=0; j
<n
; j
++){
matrix
[i
][j
] = 0;
}
}
}
for (int i
=0; i
<n
; i
++){
if (v
[i
]){
for (int j
=0; j
<m
; j
++){
matrix
[j
][i
] = 0;
}
}
}
}
}
思路二
思路二是思路一的升级版，在思路二中，我们直接将记录行、列置零的信息存放在原数组中，当然，处理起来比思路一复杂很多，但是空间复杂度为
O
(
1
)
O(1)
O(1)，因为算法中只利用了4个变量用于记录行、列置零信息；当我们遍历到 matrix[i][j] == 0 时，意味着第 i 行和第 j 列需要置零，所以我们令 matrix[i][0] = matrix[0][j] = 0，因为信息记录在了第一行第一列，所以第一行和第一列需要放到循环外面处理，对于第一行第一列是否置零，我们维护4个变量 cnt1, cnt11, cnt2, cnt22，分别表示需要置零的行数、实际置零的行数、需要置零的列数、实际置零的列数，如果 cnt11 > cnt1 ，说明第一列需要置零，同理，cnt22 > cnt2，第一行也要置零，并且对于 natrix[0][0] 还需要特殊考虑，只有当 cnt11 > cnt1 || cnt22 > cnt2 时，才需要置零；具体代码如下：
代码二
import java
.util
.Arrays
;
public class Solution {
public void setZeroes(int[][] matrix
) {
int m
= matrix
.length
, n
= 0;
if (m
> 0)
n
= matrix
[0].length
;
else
return;
int cnt1
= 0, cnt2
= 0, cnt11
= 0, cnt22
= 0;;
for (int i
=1; i
<m
; i
++){
for (int j
=1; j
<n
; j
++){
if (matrix
[i
][j
] == 0){
cnt1
+= matrix
[i
][0] != 0 ? 1:0;
cnt2
+= matrix
[0][j
] != 0 ? 1:0;
matrix
[i
][0] = matrix
[0][j
] = 0;
}
}
}
for (int i
=1; i
<m
; i
++){
if (matrix
[i
][0] == 0){
cnt11
++;
Arrays
.fill(matrix
[i
], 1, n
, 0);
}
}
for (int i
=1; i
<n
; i
++){
if (matrix
[0][i
] == 0){
cnt22
++;
for (int j
=1; j
<m
; j
++)
matrix
[j
][i
] = 0;
}
}
if (cnt22
> cnt2
|| matrix
[0][0] == 0)
Arrays
.fill(matrix
[0], 1, n
, 0);
if (cnt11
> cnt1
|| matrix
[0][0] == 0){
for (int j
=1; j
<m
; j
++)
matrix
[j
][0] = 0;
}
if (cnt11
> cnt1
|| cnt22
> cnt2
)
matrix
[0][0] = 0;
}
public static void main(String
[] args
) {
Solution solution
= new Solution();
}
}
