class Solution {
public:
void setZeroes(vector<vector<int>>& matrix) {
}
};
面试题 01.08. 零矩阵
编写一种算法，若M × N矩阵中某个元素为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] ]
原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 6.2 MB, 提交时间: 2022-11-29 16:20:39
func setZeroes(matrix [][]int) {
n, m := len(matrix), len(matrix[0])
col0 := false
for _, r := range matrix {
if r[0] == 0 {
col0 = true
}
for j := 1; j < m; j++ {
if r[j] == 0 {
r[0] = 0
matrix[0][j] = 0
}
}
}
for i := n - 1; i >= 0; i-- {
for j := 1; j < m; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
if col0 {
matrix[i][0] = 0
}
}
}
javascript 解法, 执行用时: 56 ms, 内存消耗: 43.8 MB, 提交时间: 2022-11-29 16:20:25
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let flagCol0 = false;
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
flagCol0 = true;
}
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (let i = m - 1; i >= 0; i--) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
if (flagCol0) {
matrix[i][0] = 0;
}
}
};
python3 解法, 执行用时: 40 ms, 内存消耗: 15.4 MB, 提交时间: 2022-11-29 16:19:54
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
flag_col0 = False
for i in range(m):
if matrix[i][0] == 0:
flag_col0 = True
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(m - 1, -1, -1):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if flag_col0:
matrix[i][0] = 0
python3 解法, 执行用时: 48 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-29 16:19:33
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
flag_col0 = any(matrix[i][0] == 0 for i in range(m))
flag_row0 = any(matrix[0][j] == 0 for j in range(n))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if flag_col0:
for i in range(m):
matrix[i][0] = 0
if flag_row0:
for j in range(n):
matrix[0][j] = 0
javascript 解法, 执行用时: 92 ms, 内存消耗: 44.2 MB, 提交时间: 2022-11-29 16:18:12
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
let flagCol0 = false, flagRow0 = false;
for (let i = 0; i < m; i++) {
if (matrix[i][0] === 0) {
flagCol0 = true;
}
}
for (let j = 0; j < n; j++) {
if (matrix[0][j] === 0) {
flagRow0 = true;
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][j] === 0) {
matrix[i][0] = matrix[0][j] = 0;
}
}
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (matrix[i][0] === 0 || matrix[0][j] === 0) {
matrix[i][j] = 0;
}
}
}
if (flagCol0) {
for (let i = 0; i < m; i++) {
matrix[i][0] = 0;
}
}
if (flagRow0) {
for (let j = 0; j < n; j++) {
matrix[0][j] = 0;
}
}
};
golang 解法, 执行用时: 16 ms, 内存消耗: 6.2 MB, 提交时间: 2022-11-29 16:17:39
func setZeroes(matrix [][]int) {
n, m := len(matrix), len(matrix[0])
row0, col0 := false, false
for _, v := range matrix[0] {
if v == 0 {
row0 = true
break
}
}
for _, r := range matrix {
if r[0] == 0 {
col0 = true
break
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i := 1; i < n; i++ {
for j := 1; j < m; j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if row0 {
for j := 0; j < m; j++ {
matrix[0][j] = 0
}
}
if col0 {
for _, r := range matrix {
r[0] = 0
}
}
}
golang 解法, 执行用时: 8 ms, 内存消耗: 6.2 MB, 提交时间: 2022-11-29 16:17:24
func setZeroes(matrix [][]int) {
row := make([]bool, len(matrix))
col := make([]bool, len(matrix[0]))
for i, r := range matrix {
for j, v := range r {
if v == 0 {
row[i] = true
col[j] = true
}
}
}
for i, r := range matrix {
for j := range r {
if row[i] || col[j] {
r[j] = 0
}
}
}
}
javascript 解法, 执行用时: 92 ms, 内存消耗: 44.1 MB, 提交时间: 2022-11-29 16:17:09
/**
* @param {number[][]} matrix
* @return {void} Do not return anything, modify matrix in-place instead.
*/
var setZeroes = function(matrix) {
const m = matrix.length, n = matrix[0].length;
const row = new Array(m).fill(false);
const col = new Array(n).fill(false);
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (matrix[i][j] === 0) {
row[i] = col[j] = true;
}
}
}
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
};
python3 解法, 执行用时: 36 ms, 内存消耗: 15.4 MB, 提交时间: 2022-11-29 16:16:29
'''
我们可以用两个标记数组分别记录每一行和每一列是否有零出现。
具体地，我们首先遍历该数组一次，如果某个元素为 0，
那么就将该元素所在的行和列所对应标记数组的位置置为 true。
最后我们再次遍历该数组，用标记数组更新原数组即可。
'''
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row, col = [False] * m, [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = col[j] = True
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0