友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
73. 矩阵置零
给定一个 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
进阶：
-
一个直观的解决方案是使用 \(O(mn)\) 的额外空间，但这并不是一个好的解决方案。
-
一个简单的改进方案是使用 \(O(m + n)\) 的额外空间，但这仍然不是最好的解决方案。
-
你能想出一个仅使用常量空间的解决方案吗？
思路分析
最简单的办法就是记录出现 0 的行号和列号，最后根据行号和列号设置 0。取巧的办法是把出现 0 的位置在首行和首列标记一下，首行和首列需要首先检查一下是否已经包含 0，最后再单独处理首行和首列。
-
一刷
-
二刷（路标）
-
二刷（位元素 ）
-
二刷（头部标记）
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Set Matrix Zeroes.
*
* Memory Usage: 50.4 MB, less than 5.71% of Java online submissions for Set Matrix Zeroes.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2019-10-27 00:59
*/
public void setZeroes(int[][] matrix) {
if (Objects.isNull(matrix) || matrix[0].length == 0) {
return;
}
/**
* 0 all is 0;
* 1 row is 0;
* 2 column is 0;
* 3 is not 0;
*/
int flag = 3;
int value = matrix[0][0];
if (value == 0) {
flag = 0;
}
int column = matrix.length;
int row = matrix[0].length;
for (int i = 0; i < column; i++) {
for (int j = 0; j < row; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
if (i == 0 && j > 0 && flag != 0) {
flag = 1;
}
if (i > 0 && j == 0 && flag != 0) {
if (flag == 1) {
flag = 0;
} else {
flag = 2;
}
}
}
}
}
// printMatrix(matrix);
for (int i = 1; i < column; i++) {
if (matrix[i][0] == 0) {
Arrays.fill(matrix[i], 0);
}
}
for (int j = 1; j < row; j++) {
if (matrix[0][j] == 0) {
for (int i = 0; i < column; i++) {
matrix[i][j] = 0;
}
}
}
if (flag == 0) {
Arrays.fill(matrix[0], 0);
for (int i = 0; i < column; i++) {
matrix[i][0] = 0;
}
} else if (flag == 1) {
Arrays.fill(matrix[0], 0);
} else if (flag == 2) {
for (int i = 0; i < column; i++) {
matrix[i][0] = 0;
}
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-19 20:32
*/
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// 记录 行号和列号，最后按照行号和列号来进行处理
Set<String> zeros = new HashSet<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (matrix[r][c] == 0) {
zeros.add("r" + r);
zeros.add("c" + c);
}
}
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
if (zeros.contains("r" + r) || zeros.contains("c" + c)) {
matrix[r][c] = 0;
}
}
}
}
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
55
56
57
58
59
60
61
62
63
64
65
66
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-19 21:18
*/
public void setZeroes(int[][] matrix) {
// 从数中找缺失的数字，使用缺失的数字作为占位符来处理
// 处理其他太费劲了。而且，细节太多，极易出错。
int m = matrix.length;
int n = matrix[0].length;
int size = m * n % 32 == 0 ? m * n / 32 : m * n / 32 + 1;
int cap = size * 32;
// 使用位来标记哪个数字出现过
int[] data = new int[size];
Arrays.fill(data, 0);
for (int[] ints : matrix) {
for (int r = 0; r < n; r++) {
int num = ints[r];
if (num >= cap || num < 0) {
continue;
}
int index = num / 32;
int rem = num % 32;
data[index] |= (1 << rem);
}
}
int placeholder = cap + 2;
for (int i = 0; i < data.length; i++) {
int bits = data[i];
for (int j = 0; j < 32; j++) {
// 第一个未出现的数字就是可用的占位符
if (((bits >>> j) & 1) == 0) {
placeholder = i * 32 + j;
break;
}
}
if (placeholder != cap + 2) {
break;
}
}
// 先将出现0的行列使用占位符数字标记
for (int c = 0; c < m; c++) {
for (int r = 0; r < n; r++) {
if (matrix[c][r] == 0) {
for (int ic = 0; ic < m; ic++) {
if (matrix[ic][r] != 0) {
matrix[ic][r] = placeholder;
}
}
for (int ir = 0; ir < n; ir++) {
if (matrix[c][ir] != 0) {
matrix[c][ir] = placeholder;
}
}
}
}
}
// 再统一修改为 0
for (int c = 0; c < m; c++) {
for (int r = 0; r < n; r++) {
if (matrix[c][r] == placeholder) {
matrix[c][r] = 0;
}
}
}
}
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
55
56
57
58
59
60
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-11-19 22:32
*/
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
// 第一列有没有 0
boolean rowHasZero = false;
for (int c = 0; c < m; c++) {
if (matrix[c][0] == 0) {
rowHasZero = true;
break;
}
}
// 第一行有没有 0
boolean colHasZero = false;
for (int r = 0; r < n; r++) {
if (matrix[0][r] == 0) {
colHasZero = true;
}
}
// 将出现的 0 首行和首列标记一下
for (int c = 1; c < m; c++) {
for (int r = 1; r < n; r++) {
if (matrix[c][r] == 0) {
matrix[c][0] = 0;
matrix[0][r] = 0;
}
}
}
// 根据首行和首列来修改为 0
for (int c = 1; c < m; c++) {
if (matrix[c][0] == 0) {
for (int r = 1; r < n; r++) {
matrix[c][r] = 0;
}
}
}
for (int r = 1; r < n; r++) {
if (matrix[0][r] == 0) {
for (int c = 1; c < m; c++) {
matrix[c][r] = 0;
}
}
}
// 最后处理首行和首列
if (colHasZero) {
for (int r = 0; r < n; r++) {
matrix[0][r] = 0;
}
}
if (rowHasZero) {
for (int c = 0; c < m; c++) {
matrix[c][0] = 0;
}
}
}