题目大意
#
给定一个 m * n
大小的矩阵。
要求:如果一个元素为 0
,则将其所在行和列所有元素都置为 0
。要求使用原地算法,并使用常量空间解决。
解题思路
#
直观上可以使用两个数组来标记行和列出现 0
的情况,但这样空间复杂度就是 $O(m+n)$ 了,不符合题意。
考虑使用数组原本的元素进行记录出现 0
的情况。
设定两个变量 flag_row0
、flag_col0
来标记第一行、第一列是否出现了 0
。
接下来我们使用数组第一行、第一列来标记 0
的情况。
对数组除第一行、第一列之外的每个元素进行遍历,如果某个元素出现 0
了,则使用数组的第一行、第一列对应位置来存储 0
的标记。
再对数组除第一行、第一列之外的每个元素进行遍历,通过对第一行、第一列的标记 0
情况,进行置为 0
的操作。
然后再根据 flag_row0
、flag_col0
的标记情况,对第一行、第一列进行置为 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
|
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m = len(matrix)
n = len(matrix[0])
flag_col0 = False
flag_row0 = False
for i in range(m):
if matrix[i][0] == 0:
flag_col0 = True
break
for j in range(n):
if matrix[0][j] == 0:
flag_row0 = True
break
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if flag_col0:
for i in range(m):
matrix[i][0] = 0
if flag_row0:
for j in range(n):
matrix[0][j] = 0
|