题目地址

https://leetcode.com/problems/set-matrix-zeroes/

题目描述

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]
]

• A straight forward solution using O(m**n) 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?

思路

• 先扫描第一行第一列，如果有0，则将各自的flag设置为true
• 然后扫描除去第一行第一列的整个数组，如果有0，则将对应的第一行和第一列的数字赋0
• 再次遍历除去第一行第一列的整个数组，如果对应的第一行和第一列的数字有一个为0，则将当前值赋0
• 最后根据第一行第一列的flag来更新第一行第一列

class Solution {
public:
void setZeroes(vector<vector<int> > &matrix) {
if (matrix.empty() || matrix[0].empty()) return;
int m = matrix.size(), n = matrix[0].size();
bool rowZero = false, colZero = false;
for (int i = 0; i < m; ++i) {
if (matrix[i][0] == 0) colZero = true;
}
for (int i = 0; i < n; ++i) {
if (matrix[0][i] == 0) rowZero = true;
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[i][j] == 0) {
matrix[0][j] = 0;
matrix[i][0] = 0;
}
}
}
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
if (matrix[0][j] == 0 || matrix[i][0] == 0) {
matrix[i][j] = 0;
}
}
}
if (rowZero) {
for (int i = 0; i < n; ++i) matrix[0][i] = 0;
}
if (colZero) {
for (int i = 0; i < m; ++i) matrix[i][0] = 0;
}
}
};

思路2

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;
};

• 记录下”第一行和第一列是否全是0“这样的一个数据
• 遍历除了第一行和第一列之外的所有的数据，如果是0，那就更新第一行第一列中对应的元素为0

• 根据第一行第一列的数据，更新matrix
• 最后根据我们最开始记录的”第一行和第一列是否全是0“去更新第一行和第一列即可

关键点解析

• 使用第一行和第一列来替代我们m + n 数组
• 先记录下”第一行和第一列是否全是0“这样的一个数据，否则会因为后续对第一行第一列的更新造成数据丢失
• 最后更新第一行第一列

代码

• 语言支持：JS，Python3
/*
* @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:

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)

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

扩展

https://github.com/grandyang/leetcode/ &
https://github.com/azl397985856/leetcode

评论
0 评论