矩阵置零。给定一个 m x n 的矩阵,如果一个元素为 0 ,则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。进阶:一个直观的解决方案是使用 O(mn) 的额外空间,但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m + n) 的额外空间,但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗?力扣73。
遍历除了0行和0列的数据,
第一次遍历,如果arr[i,j]==0,则arr[i][0]=0和arr[0][j]=0。
第二次遍历,如果arr[i][0]=0或者arr[0][j]=0,则arr[i,j]==0。
最后对0行和0列的数据做特殊处理。
时间复杂度:O(mn)。
额外空间复杂度:O(1)。
代码用golang编写。代码如下:
package main
import "fmt"
func main() {
if true {
matrix := [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}
setZeroes1(matrix)
fmt.Println(matrix)
}
if true {
matrix := [][]int{{1, 1, 1}, {1, 0, 1}, {1, 1, 1}}
setZeroes2(matrix)
fmt.Println(matrix)
}
}
func setZeroes1(matrix [][]int) {
row0Zero := false
col0Zero := false
i := 0
j := 0
for i = 0; i < len(matrix[0]); i++ {
if matrix[0][i] == 0 {
row0Zero = true
break
}
}
for i = 0; i < len(matrix); i++ {
if matrix[i][0] == 0 {
col0Zero = true
break
}
}
for i = 1; i < len(matrix); i++ {
for j = 1; j < len(matrix[0]); j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
matrix[0][j] = 0
}
}
}
for i = 1; i < len(matrix); i++ {
for j = 1; j < len(matrix[0]); j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if row0Zero {
for i = 0; i < len(matrix[0]); i++ {
matrix[0][i] = 0
}
}
if col0Zero {
for i = 0; i < len(matrix); i++ {
matrix[i][0] = 0
}
}
}
func setZeroes2(matrix [][]int) {
col0 := false
i := 0
j := 0
for i = 0; i < len(matrix); i++ {
for j = 0; j < len(matrix[0]); j++ {
if matrix[i][j] == 0 {
matrix[i][0] = 0
if j == 0 {
col0 = true
} else {
matrix[0][j] = 0
}
}
}
}
for i = len(matrix) - 1; i >= 0; i-- {
for j = 1; j < len(matrix[0]); j++ {
if matrix[i][0] == 0 || matrix[0][j] == 0 {
matrix[i][j] = 0
}
}
}
if col0 {
for i = 0; i < len(matrix); i++ {
matrix[i][0] = 0
}
}
}
执行结果如下: