LiaoyiLeetCode 73. 矩阵置零
题目描述
给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。
示例 1:
javascript
输入: [
[1, 1, 1],
[1, 0, 1],
[1, 1, 1],
];
输出: [
[1, 0, 1],
[0, 0, 0],
[1, 0, 1],
];
示例 2:
javascript
输入: [
[0, 1, 2, 0],
[3, 4, 5, 2],
[1, 3, 1, 5],
];
输出: [
[0, 0, 0, 0],
[0, 4, 5, 0],
[0, 3, 1, 0],
];
进阶:
javascript
一个直接的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个常数空间的解决方案吗？
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/set-matrix-zeroes 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
用 O(n) 空间复杂度来做，先遍历矩阵，找到等于 0 的坐标，然后遍历坐标，将对应行和列置为 0 即可
时间复杂度 O(m * n)
javascript
var setZeroes = function (matrix) {
let n = matrix.length;
let m = matrix[0].length;
let arr = [];
for (let i = 0; i < n; i++) {
for (let j = 0; j < m; j++) {
if (matrix[i][j] == 0) {
arr.push([i, j]);
}
}
}
while (arr.length) {
let [x, y] = arr.pop();
for (let i = 0; i < n; i++) matrix[i][y] = 0;
for (let j = 0; j < m; j++) matrix[x][j] = 0;
}
return matrix;
};
另外一种，原地算法，空间复杂度 O(1)，我们无需借助外部空间。找到下标为 0 的坐标，然后直接对该行和该列不等于 0 的数字设置为 -0 即可。这里巧妙运用了 JS 中的 Object.is()方法，此时 0 和 -0 不相等，但是最终返回的矩阵还是为 0
javascript
var setZeroes = function (matrix) {
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (Object.is(matrix[i][j], 0)) {
// 对行进行操作
for (let k = 0; k < matrix.length; k++)
if (!Object.is(matrix[k][j], 0) && k !== i) matrix[k][j] = -0;
// 对列进行操作
for (let k = 0; k < matrix[0].length; k++)
if (!Object.is(matrix[i][k], 0) && k !== j) matrix[i][k] = -0;
}
}
}
return matrix;
};
cpp
class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
int n = matrix.size();
int m = matrix[0].size();
bool row = false, col = false;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(matrix[i][j] == 0) {
if(i == 0) row = true;
if(j == 0) col = true;
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
if(matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if(row) {
for(int i = 0; i < m; i++) {
matrix[0][i] = 0;
}
}
if(col) {
for(int i = 0; i < n; i++) {
matrix[i][0] = 0;
}
}
}
};
java
class Solution {
public void setZeroes(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
boolean row = false, col = false;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(matrix[i][j] == 0) {
if(i == 0) row = true;
if(j == 0) col = true;
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
for(int i = 1; i < n; i++) {
for(int j = 1; j < m; j++) {
if(matrix[i][0] == 0 || matrix[0][j] == 0) {
matrix[i][j] = 0;
}
}
}
if(row) {
for(int i = 0; i < m; i++) {
matrix[0][i] = 0;
}
}
if(col) {
for(int i = 0; i < n; i++) {
matrix[i][0] = 0;
}
}
}
}
python
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
n = len(matrix)
m = len(matrix[0])
row = False
col = False
for i in range(n):
for j in range(m):
if matrix[i][j] == 0:
if i == 0:
row = True
if j == 0:
col = True
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, n):
for j in range(1, m):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row:
for i in range(m):
matrix[0][i] = 0
if col:
for i in range(n):
matrix[i][0] = 0
javascript
学如逆水行舟，不进则退