73.矩阵置零.go

/*
 * @lc app=leetcode.cn id=73 lang=golang
 *
 * [73] 矩阵置零
 *
 * https://leetcode-cn.com/problems/set-matrix-zeroes/description/
 *
 * algorithms
 * Medium (52.94%)
 * Likes:    98
 * Dislikes: 0
 * Total Accepted:    11.8K
 * Total Submissions: 22.3K
 * Testcase Example:  '[[1,1,1],[1,0,1],[1,1,1]]'
 *
 * 给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 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]
 * ]
 *
 * 进阶:
 *
 *
 * 一个直接的解决方案是使用  O(mn) 的额外空间，但这并不是一个好的解决方案。
 * 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
 * 你能想出一个常数空间的解决方案吗？
 *
 *
 */
func setZeroes(matrix [][]int) {
	m := len(matrix)
	if m <= 0 {
		return
	}
	n := len(matrix[0])
	if n <= 0 {
		return
	}
	colZero, rowZero := false, false
	for i := 0; i < n; i++ {
		if matrix[0][i] == 0 {
			rowZero = true
		}
	}
	for i := 0; i < m; i++ {
		if matrix[i][0] == 0 {
			colZero = true
		}
	}
	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 := m - 1; i > 0; i-- {
		for j := n - 1; j > 0; j-- {
			if matrix[i][0] == 0 {
				matrix[i][j] = 0
			}
			if matrix[0][j] == 0 {
				matrix[i][j] = 0
			}
		}
	}
	if colZero {
		for i := 0; i < m; i++ {
			matrix[i][0] = 0
		}
	}
	if rowZero {
		for i := 0; i < n; i++ {
			matrix[0][i] = 0
		}
	}

}