题目地址
题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 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]
]
进阶:
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
题解
边遍历边设置
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
if (matrix[i][j] == 0) {
fillZero(matrix, i, j);
}
}
}
}
// 如果 [m, n] 位置的元素为 0，则将其所在行和列的所有元素都设为 0
public void fillZero(int[][] matrix, int m, int n) {
if (matrix[m][n] != 0) return;
// [m, n] 所在列 n 设置为 0
for (int i = 0; i < matrix.length; ++ i) {
matrix[i][n] = 0;
}
// [m, n] 所在行 m 设置为 0
for (int j = 0; j < matrix[0].length; ++ j) {
matrix[m][j] = 0;
}
}
}
测试用例：
输入：
[[1,1,1],[1,0,1],[1,1,1]]
输出：
[[1,0,0],[0,0,0],[0,0,0]]
可以发现【边遍历边设置】会有一个问题，那就是不知道当前位置的 0 是输入中的状态还是后面设置的。
也就是说一个位置的 0 表示了两种状态：
- （1）输入时就为
0，因此需要将其所在行和列的所有元素都设为0。 - （2）输入时不为
0，因此不需要进行第（1）步的操作。
先保存状态，再设置
保存输入中为
0的点。
class Solution {
public void setZeroes(int[][] matrix) {
List<Integer> zeroPoints = new ArrayList<>();
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
if (matrix[i][j] == 0) {
int point = i * n + j;
zeroPoints.add(point);
}
}
}
for (int point : zeroPoints) {
int i = point / n;
int j = point % n;
fillZero(matrix, i, j);
}
}
// 如果 [row, column] 位置的元素为 0，则将其所在行和列的所有元素都设为 0
public void fillZero(int[][] matrix, int row, int column) {
// [row, column] 所在列 column 设置为 0
for (int i = 0; i < matrix.length; ++ i) {
matrix[i][column] = 0;
}
// [row, column] 所在行 row 设置为 0
for (int j = 0; j < matrix[0].length; ++ j) {
matrix[row][j] = 0;
}
}
}
保存保存输入中为
0的位置的行号和列号。
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[] rows = new int[m];
int[] columns = new int[n];
Arrays.fill(rows, 1);
Arrays.fill(columns, 1);
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
if (matrix[i][j] == 0) {
rows[i] = columns[j] = 0;
}
}
}
for (int i = 0; i < rows.length; ++ i) {
if (rows[i] == 0) {
fillRowZero(matrix, i);
}
}
for (int i = 0; i < columns.length; ++ i) {
if (columns[i] == 0) {
fillColumnZero(matrix, i);
}
}
}
public void fillRowZero(int[][] matrix, int row) {
// row 行设置为 0
for (int column = 0; column < matrix[0].length; ++ column) {
matrix[row][column] = 0;
}
}
public void fillColumnZero(int[][] matrix, int column) {
// column 列设置为 0
for (int row = 0; row < matrix.length; ++ row) {
matrix[row][column] = 0;
}
}
}
空间复杂度
O(m + n)。
使用矩阵第一行和第一列作为标记数组
class Solution {
public void setZeroes(int[][] matrix) {
boolean firstRowZero = false;
boolean firstColumnZero = false;
for (int row = 0; row < matrix.length; ++ row) {
if (matrix[row][0] == 0) {
firstColumnZero = true;
break;
}
}
for (int column = 0; column < matrix[0].length; ++ column) {
if (matrix[0][column] == 0) {
firstRowZero = true;
break;
}
}
int m = matrix.length;
int n = matrix[0].length;
for (int i = 0; i < m; ++ i) {
for (int j = 0; j < n; ++ j) {
if (matrix[i][j] == 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
// 填充行
for (int row = 1; row < matrix.length; ++ row) {
if (matrix[row][0] == 0) {
fillRowZero(matrix, row);
}
}
// 填充列
for (int column = 1; column < matrix[0].length; ++ column) {
if (matrix[0][column] == 0) {
fillColumnZero(matrix, column);
}
}
// 最后填充第一行或者第一列
if (firstRowZero) {
fillRowZero(matrix, 0);
}
if (firstColumnZero) {
fillColumnZero(matrix, 0);
}
}
public void fillRowZero(int[][] matrix, int row) {
// row 行设置为 0
for (int column = 0; column < matrix[0].length; ++ column) {
matrix[row][column] = 0;
}
}
public void fillColumnZero(int[][] matrix, int column) {
// column 列设置为 0
for (int row = 0; row < matrix.length; ++ row) {
matrix[row][column] = 0;
}
}
}
空间复杂度为
O(1)，因为只需要额外标记【第一行】和【第一列】是否为0即可。
网友评论