【中等】73. 矩阵置零

news/2024/12/15 7:49:20/

题目

73. 矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。

示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
你能想出一个仅使用常量空间的解决方案吗？

解题

func setZeroes(matrix [][]int)  {m := len(matrix)n := len(matrix[0])lines := [200]bool{}rows := [200]bool{}for i:=0; i<m;i++{for j:=0;j<n;j++{if matrix[i][j]==0{lines[i]=truerows[j]=true}}}for i:=0; i<m;i++{for j:=0;j<n;j++{if lines[i]==true || rows[j]==true{matrix[i][j] = 0}}}}

题解

方法一：使用标记数组

这个不难想，但是代码写的很不整洁规范

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] = truecol[j] = true}}}for i, r := range matrix {for j := range r {if row[i] || col[j] {r[j] = 0}}}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/set-matrix-zeroes/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间：O(mn)
空间：O(m+n)

方法二：使用两个标记变量

用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1)O(1) 的额外空间。

func setZeroes(matrix [][]int) {n, m := len(matrix), len(matrix[0])row0, col0 := false, falsefor _, v := range matrix[0] {if v == 0 {row0 = truebreak}}for _, r := range matrix {if r[0] == 0 {col0 = truebreak}}for i := 1; i < n; i++ {for j := 1; j < m; j++ {if matrix[i][j] == 0 {matrix[i][0] = 0matrix[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}}
}作者：力扣官方题解
链接：https://leetcode.cn/problems/set-matrix-zeroes/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。