难度: Meidum
原题连接
内容描述
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
Example 1:
Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:
Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]
Follow up:
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
思路 1 - 时间复杂度: O(row * col * (row + col))- 空间复杂度: O(row * col)******
Naive AC代码，直接复制一份matrix，边遍历边改,beats 64.75%
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
def setZero(i,j):
for m in range(col):
matrix[i][m] = 0
for n in range(row):
matrix[n][j] = 0
row = len(matrix)
col = len(matrix[0]) if row else 0
new_matrix = [matrix[i][:] for i in range(row)]
for i in range(row):
for j in range(col):
if new_matrix[i][j] == 0:
setZero(i,j)思路 2 - 时间复杂度: O(row * col)- 空间复杂度: O(row * col)******
一边遍历，一边将相应的行和列置为0是行不通的，会影响后面元素的遍历判断，
稍微优化一下空间，我们只需要记录下最后需要置为0的行index和列index即可,beats 80.11%，时间上也得到了优化
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix[0]) if row else 0
rows, cols = set(), set()
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
rows.add(i)
cols.add(j)
for i in range(row):
for j in range(col):
if i in rows or j in cols:
matrix[i][j] = 0思路 3 - 时间复杂度: O(row * col * (row + col))- 空间复杂度: O(1)******
继续优化空间，我们发现可以换一种方式把最后需要置为0的点记录下来，那就是将那个点的值先设为一个特殊值sign， 最后再来一次遍历，只要值为sign的点都置为0即可，beats 64.75%
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
sign = -sys.maxsize
row = len(matrix)
col = len(matrix[0]) if row else 0
for i in range(row):
for j in range(col):
if matrix[i][j] == 0:
# 把所有最后需要置为0的点先置为sign
for k in range(col):
matrix[i][k] = sign if matrix[i][k] != 0 else 0
for k in range(row):
matrix[k][j] = sign if matrix[k][j] != 0 else 0
for i in range(row):
for j in range(col):
# 把所有值为sign的点全部置为0
if matrix[i][j] == sign:
matrix[i][j] = 0思路 4 - 时间复杂度: O(row * col)- 空间复杂度: O(1)******
我们现在可以在思路3的基础上优化时间了，其实我们不需要记录下每一个最后需要置为0的点，而是记录下他们对应的行inde和列index就可以了， 这里用一个小trick，我们只需要将该行和该列的首元素变为0即可，第二次遍历的时候，只要一个点所处的行或者列的首元素是0，那么就将这个点置为0，
最后chekc一下第一行和第一列，不管matrix[0][0]是一开始就是0还是后面我们将它置为0的，第一行肯定都要全部置为0
对于第一列来说，我们只要之前有过一个元素在其中是0的话，整个列就需要全部置为0，之所以先check第一行再check第一列，是为了防止在这个check中将matrix[0][0]置为0了
beats 94.93%
class Solution:
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
row = len(matrix)
col = len(matrix[0]) if row else 0
set_first_col = False
for i in range(row):
if matrix[i][0] == 0:
set_first_col = True
for j in range(1, col):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, row):
for j in range(1, col):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if matrix[0][0] == 0:
for j in range(col):
matrix[0][j] = 0
if set_first_col: # 最后才判断第一列是为了防止在这个check中将matrix[0][0]置为0了
for i in range(row):
matrix[i][0] = 0