73.set-matrix-zeroes

Statement

• Difficulty: Medium
• Tag: `数组` `哈希表` `矩阵`

``````输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]

``````

``````输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]

``````

• `m == matrix.length`
• `n == matrix[0].length`
• `1 <= m, n <= 200`
• `-231 <= matrix[i][j] <= 231 - 1`

• 一个直观的解决方案是使用  `O(mn)` 的额外空间，但这并不是一个好的解决方案。
• 一个简单的改进方案是使用 `O(m + n)` 的额外空间，但这仍然不是最好的解决方案。
• 你能想出一个仅使用常量空间的解决方案吗？

• Difficulty: Medium
• Tag: `Array` `Hash Table` `Matrix`

Given an `m x n` integer matrix `matrix`, if an element is `0`, set its entire row and column to `0`'s.

You must do it in place.

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`
• `-231 <= matrix[i][j] <= 231 - 1`

• A straightforward 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?

Solution

``````from typing import List

class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
ld = {}
cd = {}
for i, l in enumerate(matrix):
for j, c in enumerate(l):
if c == 0:
ld[i] = True
cd[j] = True

for i, l in enumerate(matrix):
for j, c in enumerate(l):
if (i in ld.keys() and ld[i]) or (j in cd.keys()) and cd[j]:
matrix[i][j] = 0
``````