盒子
盒子

73_矩阵置零_leetcode

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

输入:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
输入:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

题解: 1.首行首列是否置0用额外两个变量标志 2.使用首行首列存储其他行列置0标志 3.根据首行首列标志为其他行列置0 4.根据额外变量标志置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
class Solution {
public void setZeroes(int[][] matrix) {
// 1.
boolean rowFlag = false;
boolean colFlag = false;
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
rowFlag = true;
break;
}
}
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
colFlag = true;
break;
}
}

// 2.
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}

// 3.
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
for (int j = 1; j < matrix[0].length; j++) {
matrix[i][j] = 0;
}
}
}
for (int j= 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
for (int i = 1; i < matrix.length; i++) {
matrix[i][j] = 0;
}
}
}

// 4.
if (rowFlag) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][0] = 0;
}
}
if (colFlag) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[0][j] = 0;
}
}
}
}

AC传送门leetcode
欢迎关注公众号: 算法小生

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫