做企业网站要怎么设计方案/杭州网站设计

1.题目描述

2.思路

方法1：遍历矩阵的行和列查找0元素并置同行同列的元素为0，新创建一个m*n的矩阵以标记当前的0元素是本身就为0还是被同行同列的元素传染成0的。

方法2：遍历矩阵，记录0元素的行和列，结束遍历后统一置零。

3.代码（Python3）

方法1：

import numpy as npclass Solution:def setZeroes(self, matrix: List[List[int]]) -> None:m, n = len(matrix), len(matrix[0])marked = np.ones((m, n), dtype=int)for i in range(m):for j in range(n):if matrix[i][j] == 0 and marked[i][j] != 0:for k in range(n):if matrix[i][k] != 0:matrix[i][k] = 0marked[i][k] = 0for k in range(m):if matrix[k][j] != 0:matrix[k][j] = 0marked[k][j] = 0

方法2：

class Solution:def setZeroes(self, matrix: List[List[int]]) -> None:m, n = len(matrix), len(matrix[0])zero_i, zero_j = set(), set()for i in range(m):for j in range(n):if matrix[i][j] == 0:zero_i.add(i)zero_j.add(j)for i in zero_i:for k in range(n):matrix[i][k] = 0for j in zero_j:for k in range(m):matrix[k][j] = 0

方法3：

4.执行情况

方法1：

方法2：

5.感想

方法1的空间复杂度为O(m * n)，方法2的空间复杂度为O(m + n)，官方题解使用两个标记变量的方法虽然实现了O(1)的空间复杂度但是我觉得没那个必要所以没再仔细研究。