82 lines
1.7 KiB
Markdown
82 lines
1.7 KiB
Markdown
# 矩阵置零
|
||
|
||
## 题目
|
||
|
||
|
||
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
|
||
|
||
|
||
|
||
示例 1：
|
||
|
||
|
||
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
|
||
输出：[[1,0,1],[0,0,0],[1,0,1]]
|
||
示例 2：
|
||
|
||
|
||
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
|
||
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
|
||
|
||
|
||
提示：
|
||
|
||
m == matrix.length
|
||
n == matrix[0].length
|
||
1 <= m, n <= 200
|
||
-231 <= matrix[i][j] <= 231 - 1
|
||
|
||
|
||
进阶：
|
||
|
||
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
|
||
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
|
||
你能想出一个仅使用常量空间的解决方案吗？
|
||
|
||
## 思路
|
||
|
||
- 存储
|
||
- `ArrayList<Integer>()` 存储行和列
|
||
- 更新
|
||
- 更新数组
|
||
|
||
|
||
## 代码
|
||
|
||
```java
|
||
class Solution {
|
||
public void setZeroes(int[][] matrix) {
|
||
// Init: ArrayList
|
||
Set<Integer> wide = new HashSet<>(); // n
|
||
Set<Integer> height = new HashSet<>(); // m
|
||
int m = matrix.length;
|
||
int n = matrix[0].length;
|
||
|
||
// Traverse 1: Mark
|
||
for (int i = 0; i < m; i++) {
|
||
for (int j = 0; j < n; j++) {
|
||
if (matrix[i][j] == 0) {
|
||
wide.add(j);
|
||
height.add(i);
|
||
}
|
||
}
|
||
}
|
||
// Traverse 2: Change
|
||
for (int i : height) {
|
||
for (int j = 0; j < n; j++) {
|
||
matrix[i][j] = 0;
|
||
}
|
||
}
|
||
|
||
for (int j : wide) {
|
||
for (int i = 0; i < m; i++) {
|
||
matrix[i][j] = 0;
|
||
}
|
||
}
|
||
|
||
|
||
}
|
||
}
|
||
```
|
||
|