Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
- Did you use extra space?
- 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?
Python Solution 1:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
l = [(r, c) for r, row in enumerate(matrix) for c, val in enumerate(row) if not val]
R = len(matrix)
C = len(matrix[0])
for r, c in l:
for _c in range(C):
matrix[r][_c] = 0
for _r in range(R):
matrix[_r][c] = 0
Python Solution 2:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
R = len(matrix)
C = len(matrix[0])
first_row_zero = False
for c in range(C):
if not matrix[0][c]:
first_row_zero = True
break
first_col_zero = False
for r in range(R):
if not matrix[r][0]:
first_col_zero = True
break
for r in range(1, R):
for c in range(1, C):
if not matrix[r][c]:
matrix[r][0] = matrix[0][c] = 0
for r in range(1, R):
if not matrix[r][0]:
for c in range(1, C):
matrix[r][c] = 0
for c in range(1, C):
if not matrix[0][c]:
for r in range(1, R):
matrix[r][c] = 0
if first_row_zero:
for c in range(C):
matrix[0][c] = 0
if first_col_zero:
for r in range(R):
matrix[r][0] = 0
Python Solution 3:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
R = len(matrix)
C = len(matrix[0])
first_col_zero = False
for r in range(R):
if not matrix[r][0]:
first_col_zero = True
break
for r in range(R):
for c in range(1, C):
if not matrix[r][c]:
matrix[r][0] = matrix[0][c] = 0
for r in range(R):
r = R - 1 - r
for c in range(1, C):
if not matrix[r][0] or not matrix[0][c]:
matrix[r][c] = 0
if first_col_zero:
for r in range(R):
matrix[r][0] = 0
Python Solution 4:
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
R = len(matrix)
C = len(matrix[0])
first_col_zero = False
for r in range(R):
if not matrix[r][0]: first_col_zero = True
for c in range(1, C):
if not matrix[r][c]:
matrix[r][0] = matrix[0][c] = 0
for r in range(R):
r = R - 1 - r
for c in range(1, C):
if not matrix[r][0] or not matrix[0][c]:
matrix[r][c] = 0
if first_col_zero: matrix[r][0] = 0
Summary:
- solution 4 is beautiful
LeetCode: 73. Set Matrix Zeroes
近期评论