問題描述
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: Could you devise a constant space solution?
問題分析
簡單方法:設(shè)置兩個長度分別為m和n的標(biāo)記數(shù)組分別記錄行和列是否有0,根據(jù)標(biāo)記數(shù)組將某些矩陣元素置0即供;
常數(shù)空間方法:只能申請常數(shù)空間某残,但是可以利用矩陣本身的空間來記錄信息此熬!首先記錄第1行和第1列是否需要置0龄坪,這里需要兩個常數(shù)空間來標(biāo)記腾窝,然后用第1行和第1列作為標(biāo)記數(shù)組的空間堆生,來對除第1行和第1列之外的行和列進(jìn)行記錄虐译。最后根據(jù)記錄將某些矩陣元素置0。
AC代碼
#encoding=utf-8
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
# 注釋掉的是O(mn)空間的方法
# m = len(matrix)
# if m == 0:
# return matrix
# n = len(matrix[0])
# if n == 0:
# return matrix
# flag_row = [False for i in range(m)]
# flag_column = [False for i in range(n)]
# for i in range(m):
# for j in range(n):
# if matrix[i][j] == 0:
# flag_row[i] = True
# flag_column[j] = True
# for i in range(m):
# for j in range(n):
# if flag_row[i] or flag_column[j]:
# matrix[i][j] = 0
#下面是常數(shù)空間的算法
m = len(matrix)
if m == 0:
return matrix
n = len(matrix[0])
if n == 0:
return matrix
flag_row = False
flag_column = False
#記錄第1行和第1列是否置0
for i in range(n):
if matrix[0][i] == 0:
flag_row = True
break
for j in range(m):
if matrix[j][0] == 0:
flag_column = True
break
#用第1行和第1列記錄其他行和列是否置0
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
#改變其他行和列的值
for i in range(1, m):
for j in range(1, n):
if matrix[0][j] == 0 or matrix[i][0] == 0:
matrix[i][j] = 0
#改變第一行和第一列的值
if flag_row:
for j in range(n):
matrix[0][j] = 0
if flag_column:
for i in range(m):
matrix[i][0] = 0