001.矩阵置零

• 73.矩阵置零
  • m*n 额外空间
  • m+n 额外空间
  • 两个标记变量额外空间
  • 一个标记变量额外空间

进阶：

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

矩阵置零 - m*n 额外空间

func setZeroes(matrix [][]int) {
	m := len(matrix)
	if m == 0 {
		return
	}
	n := len(matrix[0])
 
	hasZero := [][2]int{}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				hasZero = append(hasZero, [2]int{ i, j })
			}
		}
	}
 
	for _, v := range hasZero {
		setZero(matrix, v[0], v[1])
	}
}
 
func setZero(matrix [][]int, m, n int) {
	for i := range matrix[m] {
		matrix[m][i] = 0
	}
	for i := 0; i < len(matrix); i++ {
		matrix[i][n] = 0
	}
}

矩阵置零 - m+n 额外空间

func setZeroes(matrix [][]int) {
	m := len(matrix)
	if m == 0 {
		return
	}
	n := len(matrix[0])
 
	hasZero := [2][]bool{}
	hasZero[0] = make([]bool, m)
	hasZero[1] = make([]bool, n)
 
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if matrix[i][j] == 0 {
				hasZero[0][i] = true
				hasZero[1][j] = true
			}
		}
	}
 
	setZero(matrix, hasZero)
}
 
func setZero(matrix [][]int, hasZero [2][]bool) {
	for m, has := range hasZero[0] {
		if !has {
			continue
		}
		for i := range matrix[m] {
			matrix[m][i] = 0
		}
	}
 
	for n, has := range hasZero[1] {
		if !has {
			continue
		}
		for i := 0; i < len(matrix); i++ {
			matrix[i][n] = 0
		}
	}
}

矩阵置零 - 使用两个标记变量

func setZeroes(matrix [][]int) {
	m := len(matrix)
	if m == 0 {
		return
	}
	n := len(matrix[0])
 
	mHasZero, nHasZero := false, false
	for i := range matrix {
		if matrix[i][0] == 0 {
			mHasZero = true
			break
		}
	}
	for i := 0; i < n; i++ {
		if matrix[0][i] == 0 {
			nHasZero = true
			break
		}
	}
 
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[0][j] = 0
				matrix[i][0] = 0
			}
		}
	}
 
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			if matrix[0][j] == 0 || matrix[i][0] == 0 {
				matrix[i][j] = 0
			}
		}
	}
 
	if mHasZero {
		for _, v := range matrix {
			v[0] = 0
			// matrix[i][0] = 0
		}
	}
	if nHasZero {
		for i := 0; i < n; i++ {
			matrix[0][i] = 0
		}
	}
}

矩阵置零 - 使用一个标记变量

func setZeroes(matrix [][]int) {
	m := len(matrix)
	if m == 0 {
		return
	}
	n := len(matrix[0])
 
	mHasZero := false
 
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			mHasZero = true
		}
		for j := 1; j < n; j++ {
			if matrix[i][j] == 0 {
				matrix[0][j] = 0
				matrix[i][0] = 0
			}
		}
	}
 
	for i := m - 1; i >= 0; i-- {
		for j := 1; j < n; j++ {
			if matrix[0][j] == 0 || matrix[i][0] == 0 {
				matrix[i][j] = 0
			}
		}
		if mHasZero {
			matrix[i][0] = 0
		}
	}
}