Leetcode 細節實現 Set Matrix Zeroes

Leetcode 細節實現 Set Matrix Zeroes

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.

click to show follow up.

題意：給定矩陣，如果矩陣的某個位置為0，則把那一行那一列的所有元素都置為0
思路：用兩個bool數組，分別記錄應該把所有元素置為0的行和列
復雜度：時間O(m*n)，空間O(m+n)

void setZeroes(vector > &matrix){
	if(matrix.empty()) return ;
	int rows = matrix.size(), columns = matrix[0].size();
	vector row(rows, false);
	vector column(columns, false);
	for(int i = 0; i < rows; ++i){
		for(int j = 0; j < columns; ++j){
			if(matrix[i][j] == 0){
				row[i] = column[j] = true;
				continue;
			}
		}
	}
	for(int i = 0; i < rows; ++i){
		if(!row[i]) continue;
		for(int j = 0; j < columns; ++j){
			matrix[i][j] = 0;
		}
	}
	for(int j = 0; j < columns; ++j){
		if(!column[j]) continue;
		for(int i = 0; i < rows; ++i){
			matrix[i][j] = 0;
		}
	}
}