73.矩阵置零

给定一个 *m* x *n* 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法

示例 1:

img

1
2
输入:matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出:[[1,0,1],[0,0,0],[1,0,1]]

示例 2:

img

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]]

Solution

显然需要用到一种标记来表示这个零是后加的还是原生的,问题是,在要求原地算法的情况下,如何标记?题解给出了崭新的思路,利用数组本身的第1行和第1列作为标记,事先遍历记录第1行和第1列中零元素的位置,然后利用第1行和第1列作为数组置零的表示器

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length, n = matrix[0].length; // 获取矩阵的行数和列数
// 使用两个标志变量来记录第一行和第一列是否需要被置为零
boolean flagCol0 = false, flagRow0 = false;

// 检查第一列是否有零,并更新flagCol0
for (int i = 0; i < m; i++) {
if (matrix[i][0] == 0) {
flagCol0 = true;
break;
}
}

// 检查第一行是否有零,并更新flagRow0
for (int j = 0; j < n; j++) {
if (matrix[0][j] == 0) {
flagRow0 = true;
break;
}
}

// 使用第一行和第一列来记录其他行和列是否需要被置为零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}

// 根据第一行和第一列的记录来将矩阵中的元素置为零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}

// 根据flagCol0和flagRow0的值来决定是否需要将第一列和第一行置为零
if (flagCol0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
}
}