题目
结果
代码
版本一
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public void setZeroes(int[][] matrix) {
List<Coordinate> zeroes = new LinkedList<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
zeroes.add(new Coordinate(i, j));
}
}
}
for (var zero : zeroes) {
setZeroes(matrix, zero);
}
}
private void setZeroes(int[][] matrix, Coordinate zero) {
int x = zero.x;
int y = zero.y;
for (int i = 0; i < matrix[0].length; i++) {
matrix[x][i] = 0;
}
for (int i = 0; i < matrix.length; i++) {
matrix[i][y] = 0;
}
}
}
class Coordinate {
public int x;
public int y;
public Coordinate(int x, int y) {
this.x = x;
this.y = y;
}
}
|
这样会有冗余的操作，比如将同一行或一列多次置零，可以用Set改进：
版本二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class Solution {
public void setZeroes(int[][] matrix) {
Set<Integer> rows = new HashSet<>();
Set<Integer> cols = new HashSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
rows.add(i);
cols.add(j);
}
}
}
for (int row : rows) {
setZeroesR(matrix, row);
}
for (int col : cols) {
setZeroesC(matrix, col);
}
}
private void setZeroesR(int[][] matrix, int row) {
for (int i = 0; i < matrix[0].length; i++) {
matrix[row][i] = 0;
}
}
private void setZeroesC(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
}
|
Go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func setZeroes(matrix [][]int) {
flag1 := make([]bool, len(matrix))
flag2 := make([]bool, len(matrix[0]))
for i := range matrix {
for j := range matrix[i] {
if matrix[i][j] == 0 {
flag1[i] = true
flag2[j] = true
}
}
}
for i := range matrix {
for j := range matrix[i] {
if flag1[i] || flag2[j] {
matrix[i][j] = 0
}
}
}
}
|
复杂度
时间复杂度：O（M*N）
空间复杂度：O（M+N）