Leet Code OJ 73. Set Matrix Zeroes [Difficulty: Medium] -python

本文主要是介绍Leet Code OJ 73. Set Matrix Zeroes [Difficulty: Medium] -python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

73. Set Matrix Zeroes

Given an m x n matrix. If an element is 0, set its entire row and column to 0. Do it in-place.

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?

 

Example 1:

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Example 2:

 

Input: matrix = [[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]]

Constraints:

• m == matrix.length
• n == matrix[0].length
• 1 <= m, n <= 200
• -10^9 <= matrix[i][j] <= 10^9

 

题意：

把矩阵中0所在位置的对应的行或列的值全置为0；

思路1：

1.用一个空矩阵拷贝matrix的值，但是通常一般的拷贝仅仅是拷贝地址，比如a=matrix，改变a的值，matrix的值也会变，因此容易出问题。

所以我采用这种方法解决：

import copy

copy.deepcopy(matrix)

2.然后将存在0的行或者列置为0

代码如下：

#73
import copy
class Solution:def setZeroes(self, matrix):"""Do not return anything, modify matrix in-place instead."""
#        print(id(matrix))copy_m = copy.deepcopy(matrix)
#         copy = matrix.copy()
#         for i in range(len(matrix)):
#             copy.append(matrix[i])
#         print('1',copy)for i in range(len(matrix)):for j in range(len(matrix[0])):if matrix[i][j] == 0:for x in range(len(copy_m)):copy_m[x][j] = 0for y in range(len(copy_m[0])):copy_m[i][y] = 0
#                     print(copy_m)
#                     print(matrix)for i in range(len(copy_m)):for j in range(len(copy_m[0])):matrix[i][j] = copy_m[i][j]
#        print(id(matrix))
#        return matrix

注意题目说原地改变，并且不需要返回matrix，因此最后需要将值传回matrix矩阵。这个效率低，勉强通过。

思路2：

1.设置行、列两个列表，存matrix中为0的行或列的位置

2.遍历matrix，如果行或者列列表中的值为0，则设置matrix矩阵的值为0

代码如下：

#73
import copy
class Solution:def setZeroes(self, matrix):"""Do not return anything, modify matrix in-place instead."""M = len(matrix)N = len(matrix[0])raw = [1 for i in range(M)]col = [1 for i in range(N)]for i in range(M):for j in range(N):if matrix[i][j] == 0:raw[i] = 0col[j] = 0for i in range(M):for j in range(N):if raw[i]==0 or col[j]==0:matrix[i][j] = 0
#         return matrix

 

这篇关于Leet Code OJ 73. Set Matrix Zeroes [Difficulty: Medium] -python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---