254 lines
6.8 KiB
Markdown
254 lines
6.8 KiB
Markdown
## 题目地址
|
||
|
||
https://leetcode.com/problems/set-matrix-zeroes/description/
|
||
|
||
## 题目描述
|
||
|
||
```
|
||
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
|
||
|
||
Example 1:
|
||
|
||
Input:
|
||
[
|
||
[1,1,1],
|
||
[1,0,1],
|
||
[1,1,1]
|
||
]
|
||
Output:
|
||
[
|
||
[1,0,1],
|
||
[0,0,0],
|
||
[1,0,1]
|
||
]
|
||
Example 2:
|
||
|
||
Input:
|
||
[
|
||
[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]
|
||
]
|
||
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?
|
||
|
||
```
|
||
|
||
## 思路
|
||
|
||
符合直觉的想法是，使用一个 m + n 的数组来表示每一行每一列是否”全部是 0“，
|
||
先遍历一遍去构建这样的 m + n 数组，然后根据这个 m + n 数组去修改 matrix 即可。
|
||
|
||
|
||
|
||
这样的时间复杂度 O(m \* n), 空间复杂度 O(m + n).
|
||
|
||
代码如下：
|
||
|
||
```js
|
||
var setZeroes = function(matrix) {
|
||
if (matrix.length === 0) return matrix;
|
||
const m = matrix.length;
|
||
const n = matrix[0].length;
|
||
const zeroes = Array(m + n).fill(false);
|
||
|
||
for (let i = 0; i < m; i++) {
|
||
for (let j = 0; j < n; j++) {
|
||
const item = matrix[i][j];
|
||
|
||
if (item === 0) {
|
||
zeroes[i] = true;
|
||
zeroes[m + j] = true;
|
||
}
|
||
}
|
||
}
|
||
|
||
for (let i = 0; i < m; i++) {
|
||
if (zeroes[i]) {
|
||
matrix[i] = Array(n).fill(0);
|
||
}
|
||
}
|
||
|
||
for (let i = 0; i < n; i++) {
|
||
if (zeroes[m + i]) {
|
||
for (let j = 0; j < m; j++) {
|
||
matrix[j][i] = 0;
|
||
}
|
||
}
|
||
}
|
||
|
||
return matrix;
|
||
};
|
||
```
|
||
|
||
但是这道题目还有一个follow up， 要求使用O(1)的时间复杂度。因此上述的方法就不行了。
|
||
但是我们要怎么去存取这些信息（哪一行哪一列应该全部为0）呢？
|
||
|
||
一种思路是使用第一行第一列的数据来代替上述的zeros数组。 这样我们就不必借助额外的存储空间，空间复杂度自然就是O(1)了。
|
||
|
||
由于我们不能先操作第一行和第一列， 因此我们需要记录下”第一行和第一列是否全是0“这样的一个数据，最后根据这个信息去
|
||
修改第一行和第一列。
|
||
|
||
具体步骤如下：
|
||
|
||
- 记录下”第一行和第一列是否全是0“这样的一个数据
|
||
- 遍历除了第一行和第一列之外的所有的数据，如果是0，那就更新第一行第一列中对应的元素为0
|
||
> 你可以把第一行第一列看成我们上面那种解法使用的m + n 数组。
|
||
- 根据第一行第一列的数据，更新matrix
|
||
- 最后根据我们最开始记录的”第一行和第一列是否全是0“去更新第一行和第一列即可
|
||
|
||
|
||
|
||
|
||
## 关键点
|
||
- 使用第一行和第一列来替代我们m + n 数组
|
||
- 先记录下”第一行和第一列是否全是0“这样的一个数据，否则会因为后续对第一行第一列的更新造成数据丢失
|
||
- 最后更新第一行第一列
|
||
## 代码
|
||
|
||
* 语言支持：JS，Python3
|
||
|
||
```js
|
||
/*
|
||
* @lc app=leetcode id=73 lang=javascript
|
||
*
|
||
* [73] Set Matrix Zeroes
|
||
*/
|
||
/**
|
||
* @param {number[][]} matrix
|
||
* @return {void} Do not return anything, modify matrix in-place instead.
|
||
*/
|
||
var setZeroes = function(matrix) {
|
||
if (matrix.length === 0) return matrix;
|
||
const m = matrix.length;
|
||
const n = matrix[0].length;
|
||
|
||
// 时间复杂度 O(m * n), 空间复杂度 O(1)
|
||
let firstRow = false; // 第一行是否应该全部为0
|
||
let firstCol = false; // 第一列是否应该全部为0
|
||
|
||
for (let i = 0; i < m; i++) {
|
||
for (let j = 0; j < n; j++) {
|
||
const item = matrix[i][j];
|
||
if (item === 0) {
|
||
if (i === 0) {
|
||
firstRow = true;
|
||
}
|
||
if (j === 0) {
|
||
firstCol = true;
|
||
}
|
||
matrix[0][j] = 0;
|
||
matrix[i][0] = 0;
|
||
}
|
||
}
|
||
}
|
||
|
||
for (let i = 1; i < m; i++) {
|
||
for (let j = 1; j < n; j++) {
|
||
const item = matrix[i][j];
|
||
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
|
||
matrix[i][j] = 0;
|
||
}
|
||
}
|
||
}
|
||
|
||
// 最后处理第一行和第一列
|
||
|
||
if (firstRow) {
|
||
for (let i = 0; i < n; i++) {
|
||
matrix[0][i] = 0;
|
||
}
|
||
}
|
||
|
||
if (firstCol) {
|
||
for (let i = 0; i < m; i++) {
|
||
matrix[i][0] = 0;
|
||
}
|
||
}
|
||
|
||
return matrix;
|
||
};
|
||
```
|
||
Python3 Code:
|
||
|
||
直接修改第一行和第一列为0的解法：
|
||
```python
|
||
class Solution:
|
||
def setZeroes(self, matrix: List[List[int]]) -> None:
|
||
"""
|
||
Do not return anything, modify matrix in-place instead.
|
||
"""
|
||
def setRowZeros(matrix: List[List[int]], i:int) -> None:
|
||
C = len(matrix[0])
|
||
matrix[i] = [0] * C
|
||
|
||
def setColZeros(matrix: List[List[int]], j:int) -> None:
|
||
R = len(matrix)
|
||
for i in range(R):
|
||
matrix[i][j] = 0
|
||
|
||
isCol = False
|
||
R = len(matrix)
|
||
C = len(matrix[0])
|
||
|
||
for i in range(R):
|
||
if matrix[i][0] == 0:
|
||
isCol = True
|
||
for j in range(1, C):
|
||
if matrix[i][j] == 0:
|
||
matrix[i][0] = 0
|
||
matrix[0][j] = 0
|
||
for j in range(1, C):
|
||
if matrix[0][j] == 0:
|
||
setColZeros(matrix, j)
|
||
|
||
for i in range(R):
|
||
if matrix[i][0] == 0:
|
||
setRowZeros(matrix, i)
|
||
|
||
if isCol:
|
||
setColZeros(matrix, 0)
|
||
|
||
```
|
||
|
||
另一种方法是用一个特殊符合标记需要改变的结果，只要这个特殊标记不在我们的题目数据范围（0和1）即可，这里用None。
|
||
```python
|
||
class Solution:
|
||
def setZeroes(self, matrix: List[List[int]]) -> None:
|
||
"""
|
||
这题要解决的问题是，必须有个地方记录判断结果，但又不能影响下一步的判断条件；
|
||
直接改为0的话，会影响下一步的判断条件；
|
||
因此，有一种思路是先改为None，最后再将None改为0；
|
||
从条件上看，如果可以将第一行、第二行作为记录空间，那么，用None应该也不算违背题目条件；
|
||
"""
|
||
rows = len(matrix)
|
||
cols = len(matrix[0])
|
||
# 遍历矩阵，用None记录要改的地方，注意如果是0则要保留，否则会影响下一步判断
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if matrix[r][c] is not None and matrix[r][c] == 0:
|
||
# 改值
|
||
for i in range(rows):
|
||
matrix[i][c] = None if matrix[i][c] != 0 else 0
|
||
for j in range(cols):
|
||
matrix[r][j] = None if matrix[r][j] != 0 else 0
|
||
# 再次遍历，将None改为0
|
||
for r in range(rows):
|
||
for c in range(cols):
|
||
if matrix[r][c] is None:
|
||
matrix[r][c] = 0
|
||
```
|
||
|
||
## 扩展
|
||
|
||
为什么选择第一行第一列，选择其他行和列可以么？为什么？
|