给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
这道题麻烦的地方是要注意不能使得因为其他元素变为0的元素 再去影响其他元素 我先遍历整个矩阵标记为0的位置 直接置0
还有一点就是不能因为这个元素 使得其他本来应该影响到其他元素的 没有被影响
来写代码
class Solution(object):
def setZeroes(self, matrix):
m=len(matrix)
n=len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j]==0:
matrix[i][j]=True
#要注意置为0的时候不能让其他的ture的变为0
for i in range(m):
for j in range(n):
if matrix[i][j]==True:
matrix[i][j] =0#将这个元素先置为0
for t in range(n):
if matrix[i][t]!=True:
matrix[i][t]=0
for s in range(m):
if matrix[s][j]!=True:
matrix[s][j]=0
return matrix
solution=Solution()
result=solution.setZeroes([[1,1,1],[1,0,1],[1,1,1]])
print(result)
结果是错误的 我有点迷茫 在第一轮的时候 我是设置好了 中间那个元素是true的 其他元素我也没有修改 然后等到下一轮的时候 只有中间那个元素是0 设置为true了我先将这个元素设置为0 然后在这一行的元素如果不是true的话 就设置为0 这一列也是 如果不是true的话 就设置为0 我不知道哪里出问题了 打印出来看看
[[1, 1, 1], [1, True, 1], [1, 1, 1]]
[[0, 0, 0], [0, 0, 0], [0, 0, 0]]
第一轮没啥问题 那么问题出在第二轮
for i in range(m):
for j in range(n):
if matrix[i][j]==True:
matrix[i][j] =0#将这个元素先置为0
for t in range(n):
if matrix[i][t]!=True:
matrix[i][t]=0
for s in range(m):
if matrix[s][j]!=True:
matrix[s][j]=0
分析这个哪里出问题了？
okok没的问题 我彻底被自己蠢哭了 元素0就不是true啊 我真服了 忘记了数字对应的true和false的情况 我真想扇自己一巴掌
class Solution(object):
def setZeroes(self, matrix):
m=len(matrix)
n=len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j]==0:
matrix[i][j]='True'
print(matrix)
#要注意置为0的时候不能让其他的ture的变为0
for i in range(m):
for j in range(n):
if matrix[i][j]=='True':
matrix[i][j] =0#将这个元素先置为0
for t in range(n):
if matrix[i][t]!='True':
matrix[i][t]=0
for s in range(m):
if matrix[s][j]!='True':
matrix[s][j]=0
return matrix
solution=Solution()
result=solution.setZeroes([[1,1,1],[1,0,1],[1,1,1]])
print(result)
使用特殊一点的标记就行 我真的 我哭死 我的脑子全都是浆糊了 虽然这个通过了 但是效率很低 我们来进行优化
就是我们应该是做过类似的题目的 就是使用矩阵本身进行存储 因为就算是使得矩阵全部置0 也只是m行n列 所以我使用m+n-1个元素绝对够了 也就是第一行第一列就是绝对够了
就比如 matrix[i][j]==0 那么我就设置第一列的i素为‘z’ 就表示这一行是要变为0的 设置第一行的 为‘z’
表示这一列是要变为0的 但是要注意原本这个元素是不是0 如果是的话 先把这个的给置为0
思考一下 这样会不会影响到第一行和第一列的 如果在这一列中有元素为0 那么在第一行的这个元素也应该为0 如果没有这行这列为0 那么也不会影响到第一行和第一列的元素 所以没有影响
所以先看在第一行第一列的是啥情况 然后再看其他位置的是啥情况 好的我们来写代码
class Solution(object):
def setZeroes(self, matrix):
m=len(matrix)
n=len(matrix[0])
flag=''
flag1=''
for i in range(m):
if matrix[i][0]==0:
matrix[i][0]='True'
flag='True'#第0列
for j in range(n):
if matrix[0][j]==0:
matrix[0][j]='True'
flag1='True'#第0行
print(matrix)
for i in range(1,m):
for j in range(1,n):
if matrix[i][j]==0:
matrix[i][0]='True'
matrix[0][j] = 'True'
for i in range(1,m):
if matrix[i][0]=='True':
matrix[i]=[0]*n
for j in range(1,n):
if matrix[0][j]=='True':
for i in range(m):
matrix[i][j]=0
print(flag,'+',flag1)
if flag=='True' :
for i in range(m):
matrix[i][0]=0
if flag1=='True' :
matrix[0] = [0]*n
# 针对于这一行 其实针对的是列
return matrix
solution=Solution()
result=solution.setZeroes([[0,1]])
print(result)
但是这个针对于[0,1]的情况就有问题 所以我们需要再分析一下 如果是[0,0]处为0 那么我认为是列为0设置为true了 那么列就改变不了了 所以这个要特殊处理
class Solution(object):
def setZeroes(self, matrix):
m=len(matrix)
n=len(matrix[0])
flag=''
flag1=''
for i in range(m):
if matrix[i][0]==0:
matrix[i][0]='True'
flag = 'True' # 第0列
if i==0:
flag1='True'#在这里修改了一下
for j in range(n):
if matrix[0][j]==0:
matrix[0][j]='True'
flag1='True'#第0行
print(matrix)
for i in range(1,m):
for j in range(1,n):
if matrix[i][j]==0:
matrix[i][0]='True'
matrix[0][j] = 'True'
for i in range(1,m):
if matrix[i][0]=='True':
matrix[i]=[0]*n
for j in range(1,n):
if matrix[0][j]=='True':
for i in range(m):
matrix[i][j]=0
print(flag,'+',flag1)
if flag=='True' :
for i in range(m):
matrix[i][0]=0
if flag1=='True' :
matrix[0] = [0]*n
# 针对于这一行 其实针对的是列
return matrix
solution=Solution()
result=solution.setZeroes([[0,1]])
print(result)
在写这个代码的过程中 也是进行了多次的修改 其中就有因为浅拷贝 深拷贝弄了很多的错误 这个大家自己可以去了解一下
但是很不幸的是 我修改之后的运行速度也依旧垃圾 我看了前面耗时少的 大部分都是使用集合 还是集合好啊 拿出来一个空间直接将进行标记就行 我们来分析一个例子
class Solution(object):
def setZeroes(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
rows = set()
columns = set()#存起来
for i in range(len(matrix)):
for j in range(len(matrix[0])):
if matrix[i][j] == 0:
rows.add(i)
columns.add(j)#记录
for i in rows:#对这些列
for j in range(len(matrix[0])):
matrix[i][j] = 0
for j in columns:#对这些行
for i in range(len(matrix)):
matrix[i][j] = 0
可以的 兄弟们 都可以的
如果喜欢这个帖子 欢迎点赞收藏 俺虽然用了最傻呗的方法 但是起码还是做出来了 泪目了