73-矩阵置零

73、矩阵置零

https://leetcode-cn.com/problems/set-matrix-zeroes/

题目:

axZSMT.png

题解:

此题主要考点是如何减少空间复杂度,原地将矩阵该置零的位置置零。思路是先判断第一列和第一行是否有零,用两个布尔变量来记录这一结果。然后遍历除第一行和第一列的整个矩阵,一旦发现零,就在第一行和第一列的对应位置上置零。这样记录完毕后,再次遍历一边,只要发现对应位置上的第一行或第一列有0,则说明此点的行和列应被清零。最后,根据两个布尔变量,判断第一行和第一列是否需要清零即可。

Leetcode解题大佬真滴牛,学习了学习了。

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
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row0_flag = False
col0_flag = False
for i in range(len(matrix)):
if matrix[i][0] == 0:
col0_flag = True
break
for i in range(len(matrix[0])):
if matrix[0][i] == 0:
row0_flag = True
break
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0

for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row0_flag == True:
for i in range(len(matrix[0])):
matrix[0][i] = 0
if col0_flag == True:
for i in range(len(matrix)):
matrix[i][0] = 0

当前网速较慢或者你使用的浏览器不支持博客特定功能,请尝试刷新或换用Chrome、Firefox等现代浏览器