Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?

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?

提示	解題應用
Array	Array/Slice

Default:

func setZeroes(matrix [][]int) {

}

解答思路:

正如Follow up所述，一開始就想直接用mxn與資料相同的陣列大小來各別儲存所有0的位置，再好一點的作法就是只用m+n格陣列，如果[x,y]的位置為0就在m[x]與n[y]註記該行與列要全為0，至於最好的做法就是不再另外用空間來儲存0的位置，而是直接在資料陣列上註記，也就是說如果[x,y]的位置為0就將[x,0]與[0,y]原本的值取代為0(順便紀鍵最上方的橫排[0~m-1,0]與最左方的直列[0,0~n-1]原始值是否有任一個為值為0)，接著只遍歷[1,1] ~ [m-1,n-1]，如果某位置[x,y]發現[x,0]或[0,y]任一位置的值為0，就將[x,y]原本的值取代為0，最後如果[0~m-1,0]與[0,0~n-1]先前所註記該橫排或直列存在0的值，就將該橫排或直列的所有值取代為0。

程式碼解說:

如先前思路所述，為了不使用任何額外空間，要直接在資料陣列上註記哪行與哪列要全為0，所以一開始便遍歷整個二元陣列，如果[x,y]的位置為0就將[x,0]與[0,y]原本的值取代為0，稍後便能藉由這些0的位置來知道要將哪行或哪列上的所有值取代為0，而在確定該位置的值為0同時如果是x為0就註記最後要將最上方橫排的全部元素取代為0，如果是y為0就註記最後要將最左方直列的全部元素取代為0

var row bool
var col bool
for i := 0; i < len(matrix); i++ {
	for j := 0; j < len(matrix[0]); j++ {
		if matrix[i][j] == 0 {
			if i == 0 {
				row = true
			}
			if j == 0 {
				col = true
			}
			matrix[i][0] = 0
			matrix[0][j] = 0
		}
	}
}

在註記完哪行與哪列要全為0後，接著從[1,1] ~ [m-1,n-1]，如果某位置[x,y]發現[x,0]或[0,y]任一位置的值為0，就將[x,y]原本的值取代為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
		}
	}
}

最後只剩最上方的橫排[0~m-1,0]與最左方的直列[0,0~n-1]還未判斷，藉由先前所註記該橫排或直列存在0的值，就將該橫排或直列的所有值取代為0

if col {
	for i := 0; i < len(matrix); i++ {
		matrix[i][0] = 0
	}
}
if row {
	for j := 0; j < len(matrix[0]); j++ {
		matrix[0][j] = 0
	}
}

完整程式碼:

func setZeroes(matrix [][]int) {
	var row bool
	var col bool
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			if matrix[i][j] == 0 {
				if i == 0 {
					row = true
				}
				if j == 0 {
					col = true
				}
				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 col {
		for i := 0; i < len(matrix); i++ {
			matrix[i][0] = 0
		}
	}
	if row {
		for j := 0; j < len(matrix[0]); j++ {
			matrix[0][j] = 0
		}
	}
}

總結:

在mxn的二元陣列中，若任一值為0則將該值位置上行與列的所有元素取代為0，最好的做法就是不再另外用空間來儲存0的位置，而是直接在資料陣列上註記，也就是說如果[x,y]的位置為0就將[x,0]與[0,y]原本的值取代為0(順便紀鍵最上方的橫排[0~m-1,0]與最左方的直列[0,0~n-1]原始值是否有任一個為值為0)，接著只遍歷[1,1] ~ [m-1,n-1]，如果某位置[x,y]發現[x,0]或[0,y]任一位置的值為0，就將[x,y]原本的值取代為0，最後如果[0~m-1,0]與[0,0~n-1]先前所註記該橫排或直列存在0的值，就將該橫排或直列的所有值取代為0。