LeetCode 73. 矩阵置零

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

🔥 73. 矩阵置零

思路分析

首先，我们需要确定哪些行和列需要被置为 0。可以使用两个布尔数组 rows 和 cols 来记录需要置为 0 的行和列。

遍历矩阵，找到所有为 0 的元素，并将对应的行和列标记为 true。

再次遍历矩阵，根据 rows 和 cols 数组的标记，将对应的元素置为 0。

参考代码

func setZeroes(matrix [][]int) {
	if len(matrix) == 0 {
		return
	}

	m, n := len(matrix), len(matrix[0])
	rows := make([]bool, m)
	cols := make([]bool, n)

	// 第一次遍历，记录需要置为 0 的行和列
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				rows[i] = true
				cols[j] = true
			}
		}
	}

	// 第二次遍历，置为 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if rows[i] || cols[j] {
				matrix[i][j] = 0
			}
		}
	}
}

时间复杂度：O (m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们遍历了每个元素两次。

空间复杂度：O (m + n)，使用了两个布尔数组来记录行和列的状态。

🍏 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/73238111