给定一个 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] ]
- 一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个常数空间的解决方案吗
解法：
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142object SetZeroes {
def main(args: Array[String]): Unit = {
val matrix = Array[Array[Int]](
Array[Int](1, 1, 1),
Array[Int](1, 0, 1),
Array[Int](1, 1, 1)
)
setZeroes1(matrix)
matrix.foreach(a => {
println(java.util.Arrays.toString(a))
})
val matrix2 = Array[Array[Int]](
Array[Int](0, 1, 2, 0),
Array[Int](3, 4, 5, 2),
Array[Int](1, 3, 1, 5)
)
setZeroes2(matrix2)
matrix2.foreach(a => {
println(java.util.Arrays.toString(a))
})
val matrix3 = Array[Array[Int]](
Array[Int](0, 1, 2, 0),
Array[Int](3, 4, 5, 2),
Array[Int](1, 3, 1, 5)
)
setZeroes2(matrix3)
matrix3.foreach(a => {
println(java.util.Arrays.toString(a))
})
}
/**
* 空间复杂度O(m*n)
*/
def setZeroes1(matrix: Array[Array[Int]]): Unit = {
val indexs = new ListBuffer[(Int, Int)]()
val m = matrix.length
if (m == 0) {
return
}
val n = matrix(0).length
for (i <- 0 until m) {
for (j <- 0 until n) {
if (matrix(i)(j) == 0) {
indexs += ((i, j))
}
}
}
indexs.foreach(a => {
for (i <- 0 until n) {
matrix(a._1)(i) = 0
}
for (i <- 0 until m) {
matrix(i)(a._2) = 0
}
})
}
/**
* 空间复杂度O(m + n)
*/
def setZeroes2(matrix: Array[Array[Int]]): Unit = {
var rows = List[Int]()
var cols = List[Int]()
val m = matrix.length
if (m == 0) {
return
}
val n = matrix(0).length
for (i <- 0 until m) {
for (j <- 0 until n) {
if (matrix(i)(j) == 0) {
rows ::= i
cols ::= j
}
}
}
rows.foreach(row => {
for (i <- 0 until n) {
matrix(row)(i) = 0
}
})
cols.foreach(col => {
for (i <- 0 until m) {
matrix(i)(col) = 0
}
})
}
/**
* 空间复杂度O(1)
*/
def setZeroes3(matrix: Array[Array[Int]]): Unit = {
val m = matrix.length
if (m == 0) {
return
}
val n = matrix(0).length
for (i <- 1 until m) {
for (j <- 1 until n) {
if (matrix(i)(j) == 0) {
matrix(i)(0) = 0
matrix(0)(j) = 0
}
}
}
for (i <- 0 until m) {
if (matrix(i)(0) == 0) {
for (j <- 0 until n) {
matrix(i)(j) == 0
}
}
}
for (i <- 0 until n) {
if (matrix(0)(i) == 0) {
for (j <- 0 until m) {
matrix(j)(i) == 0
}
}
}
}
}