[LeetCode] 73. Set Matrix Zeroes

轉自LeetCode

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?

<Solution>

這題的題意是說，如果 matrix[i][j] = 0，則 row i 和 col j 上的值都要變成 0

例如

0 1 1 0    0 0 0 0
2 0 2 2 => 0 0 0 0
3 3 3 3    0 0 3 0

那題目也有要求，要 in place，且是不是可以不用到額外的空間

想法如下

• 使用 first row 和 first col 來記錄之後會變成 0 的 row 和 col。舉例

1 1 1 1
2 2 0 2 => matrix[1][2] = 0，這時候先將 matrix[0][2] 和 matrix[1][0] 都設為 0
3 3 3 3

1 1 0 1
0 2 0 2 => 這樣之後只要檢查 first row 和 first col，就會知道該 row 和該 col 是否要變為 0
3 3 3 3

• 因為把 first row 和 first col 拿來記錄用，所以要先檢查 first row 和 first col 本身需不需要全部變為 0

code 如下

	class Solution {
	public:
	void setZeroes(vector<vector<int>>& matrix) {
	if(matrix.empty()) {
	return;
	}
	const int m = matrix.size(), n = matrix[0].size();
	bool firstRowHasZero = false, firstColHasZero = false;
	//> we will use first row and first col to record 0's element
	//> so check first row and first col have 0 element or not
	for(int c = 0; c < n; c++) {
	if(matrix[0][c] == 0) {
	firstRowHasZero = true;
	break;
	}
	}
	for(int r = 0; r < m; r++) {
	if(matrix[r][0] == 0) {
	firstColHasZero = true;
	break;
	}
	}
	//> check others elements
	for(int r = 1; r < m; r++) {
	for(int c = 1; c < n; c++) {
	if(matrix[r][c] == 0) {
	matrix[0][c] = 0;
	matrix[r][0] = 0;
	}
	}
	}
	//> change to zero matrix
	for(int r = 1; r < m; r++) {
	for(int c = 1; c < n; c++) {
	if(matrix[0][c] == 0 || matrix[r][0] == 0) {
	matrix[r][c] = 0;
	}
	}
	}
	//> finally, check first row and first col
	if(firstRowHasZero) {
	for(int c = 0; c < n; c++) {
	matrix[0][c] = 0;
	}
	}
	if(firstColHasZero) {
	for(int r = 0; r < m; r++) {
	matrix[r][0] = 0;
	}
	}
	}
	};

view raw setMatrixZeros.cpp hosted with ❤ by GitHub