题目
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.
题意
题目很好理解，就是给定一个矩阵，其中出现0的行列也全部置0
例子
Input:
[ [0,1,2,0], [3,4,5,2], [1,3,1,5] ]
Output:
[ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
Follow up:
- A straight forward solution using O(mn) space is probably a bad idea.
- A simple improvement uses O(m + n) space, but still not the best solution.
- Could you devise a constant space solution?
解法
这道题可以先找出元素为0的行列，然后再将这些行列赋值为0；这种情况需要额外的空间来存在行列，最多需要m+n；这里提示说可以不使用额外的存储空间来完成。
我们可以用第一行第一列来标记那些需要被置0的行列，因为当矩阵中出现元素为0时，行列都为0，第一行第一列对应的位置也为0，所以就是相当于先将第一行第一列置为0，然后在遍历数组，如果某个元素其所在位置行列第一位为0，则将其置0；主要考虑一种情况，就第一行或第一列全为0，那么需要标记，待其他行列都置0后才置第一列行，否则整个矩阵都会被置0；
代码
解法一
var Row,Line int
func setZeroes(matrix [][]int) {
Row = len(matrix)
if Row == 0 {
return
}
Line = len(matrix[0])
if Line == 0{
return
}
zeros := make([]int,0) //保存0元素行列
for i:=0;i<Row;i++{
for j:=0;j<Line;j++{
if matrix[i][j]==0{
zeros = append(zeros,i,j)
}
}
}
for i:=0;i<len(zeros);i=i+2{
SetZero(matrix,zeros[i],zeros[i+1])
}
}
func SetZero(matrix [][]int,row int,line int){
for i:=0;i<Line;i++{
matrix[row][i]=0
}
for i:=0;i<Row;i++{
matrix[i][line]=0
}
}
解法2
func setZeroes(matrix [][]int) {
Row := len(matrix)
if Row == 0 {
return
}
Line := len(matrix[0])
if Line == 0{
return
}
//第一行列是否置0
RowFirstZero := false
LineFirstZero := false
for i:=0;i<Row;i++{
for j:=0;j<Line;j++{
if matrix[i][j]==0{
if i==0{
RowFirstZero=true
}
if j==0{
LineFirstZero=true
}
//将0行列第一位置0
matrix[0][j]=0
matrix[i][0]=0
}
}
}
for i:=1;i<Row;i++{
for j:=1;j<Line;j++{
if matrix[0][j]==0{
matrix[i][j]=0
}
if matrix[i][0]==0{
matrix[i][j]=0
}
}
}
if RowFirstZero{
for i:=0;i<Line;i++{
matrix[0][i]=0
}
}
if LineFirstZero{
for i:=0;i<Row;i++{
matrix[i][0]=0
}
}
}
总结
这道题一开始没多想，直接使用存储行列的方式来做，时间复杂度超越100%，但是空间复杂度只超越15.38%。查了别人的利用原数组的方法后，根据该方法又重新提交了一遍，发现空间复杂度竟然差不多。不吐槽了。。。
这道题就是需要灵活转变吧，能够想到利用第一行第一列来作为置0行列的标志。
