LeetCode题目笔记——面试题 01.08. 零矩阵

题目描述——截图

题目描述——文字

  编写一种算法，若M × N矩阵中某个元素为0，则将其所在的行与列清零。

示例 1：

输入： [ [1,1,1], [1,0,1], [1,1,1] ] 输出： [ [1,0,1], [0,0,0], [1,0,1] ]
示例 2：

输入： [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出： [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zero-matrix-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目难度——中等

方法一

  注意题目要求是要在原数组上进行修改，我们不能重新创建一个数组再将其作为答案返回。可能有小伙伴看到题目想到的是一边遍历，一边置零，这是行不通的，因为在前面遍历碰到0就将所在行列置零的话，后面再访问到那个元素时，就不是原来的那个元素了，所以不能遍历的同时进行修改。
  所以可以用额外的空间来解决，我们先遍历一遍矩阵，记录有0的行和列的下标，遍历过后再对这些行和列进行遍历，将他们所在的行和列的元素置零。

代码——Python

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        zerorow = set()
        zerocol = set()
        M = len(matrix)
        N = len(matrix[0])
        for i in range(M):
            for j in range(N):
                if matrix[i][j] == 0:
                    zerorow.add(i)
                    zerocol.add(j)
        for r in zerorow:
            for col in range(N):
                matrix[r][col] = 0
        
        for c in zerocol:
            for row in range(M):
                matrix[row][c] = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结

  该方法首先要遍历一遍矩阵，因此时间是O(MN)，使用了额外的数据结构来存储要修改的行列，所以空间是O(M+N)。40ms，打败了88%，看了一下前面20多ms的，其实思路也是一样的，我的代码还要简单一点，LeetCode的计时有点玄学。