前言
新的一年，好好学习
正文
问题来源
本问题来自leetcode上的73题。
问题描述
给定一个 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) {
flag := false
y := make([]int, 0)
for i := 0; i < len(matrix); i++ {
for j := 0; j < len(matrix[0]); j++ {
if 0 == matrix[i][j] {
y = append(y, j)
flag = true
}
}
if true == flag {
for j := 0; j < len(matrix[0]); j++ {
matrix[i][j] = 0
}
}
flag = false
}
for i := 0; i < len(y); i++ {
for j := 0; j < len(matrix); j++ {
matrix[j][y[i]] = 0
}
}
}
这样写法的问题，一空间复杂度高，二没有去重行号。
网上给出的算法(python实现)
用第一行和第一列记录这一行和这一列中是否有零，当然，一开始要先用row和col记录第一行和第一列是否有零，最后再根据这个判断是否将第一行第一列置零
class Solution:
# @param matrix, a list of lists of integers
# @return nothing (void), do not return anything, MODIFY matrix IN PLACE.
def setZeroes(self, matrix):
if len(matrix) == 0:
return ;
row, col = 1, 1
for i in range(0, len(matrix)):
if matrix[i][0] == 0:
col = 0
for j in range(0, len(matrix[0])):
if matrix[0][j] == 0:
row = 0
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, len(matrix)):
for j in range(1, len(matrix[0])):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if col == 0:
for i in range(0, len(matrix)):
matrix[i][0] = 0
if row == 0:
for j in range(0, len(matrix[0])):
matrix[0][j] = 0
总结：
勤思考。
结语
不管怎么样好好加油。
