image.png
我的原始思路，两个额外的数组分别标记需要置零的行&列。
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
col_flag = [False for i in range(len(matrix[0]))]
row_flag = [False for i in range(len(matrix))]
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
row_flag[i]=True
col_flag[j]=True
for i in range(len(row_flag)):
if row_flag[i]:
matrix[i]=[0]*len(matrix[i])
for i in range(len(col_flag)):
if col_flag[i]:
for k in range(len(matrix)):
matrix[k][i]=0
return matrix
image.png
- 代码优化：
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
r = len(matrix)
c = len(matrix[0])
col_flag = [False for i in range(c)]
row_flag = [False for i in range(r)]
for i in range(r):
for j in range(c):
if matrix[i][j] == 0:
row_flag[i]=True
col_flag[j]=True
for i in range(r):
for j in range(c):
if row_flag[i] or col_flag[j]:
matrix[i][j]=0
return matrix
image.png
时间复杂度：O(mn) --- 难以优化
空间复杂度： O(m+n) --- 优化思路：可以利用矩阵的第一行，第一列做标记，再单独用两个变量标记第一行/列。
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
r = len(matrix)
c = len(matrix[0])
col_flag=False
row_flag=False
for j in range(c):
if matrix[0][j]==0:
row_flag=True
for j in range(r):
if matrix[j][0]==0:
col_flag=True
for i in range(1,r):
for j in range(1,c):
if matrix[i][j] == 0:
matrix[i][0]=0
matrix[0][j]=0
for i in range(1,r):
for j in range(1,c):
if matrix[i][0]==0 or matrix[0][j]==0:
matrix[i][j]=0
if row_flag:
for i in range(c):
matrix[0][i]=0
if col_flag:
for i in range(r):
matrix[i][0]=0
return matrix
image.png
