LeetCode 热题 100_矩阵置零(18_73_中等_C++)（哈希集合；使用原二维数组记录）

题目描述：

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

输入输出样例：

示例 1：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

提示：
m== matrix.length
n == matrix[0].length
1 <= m, n <= 200
-2³¹ <= matrix[i][j] <= 2³¹ - 1

进阶：
一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。

一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。

你能想出一个仅使用常量空间的解决方案吗？

题解：

解题思路：

思路一（哈希集合）：

1、通过题目分析，只要某一个位置出现0，则该位置所在的行和列中的所有元素都置0。我们不能一边记录一边置0，容易导致该行列中的其他信息的丢失。 所以先记录0的位置，再进行变换。

2、具体思路如下：
① 只要一行中出现至少一个0我们就可以将这一行置为0，我们可以使用两个unordered_set，来分别存储需要归零的行和列（防止重复）。
② 最后通过两个unordered_set来进行矩阵置零 。

2、复杂度分析：
① 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。遍历了一遍数组 mn。行列置0最坏的情况是遍历整个数组两次（2mn）。
② 空间复杂度：O(m+n)，最坏的情况是每行，每列都需要记录置0。

思路二（使用原二维数组记录置0信息）：

1、这时我们需要拿出一行和一列来存放置本行或列是否置0（采用第一行和第一列来记录）。此时我们需要用到第一行row[0]和第一列column[0]来记录（若第一行或第一列存0，则对应行或列置0，若！=0无需变换）。在记录之前需要判断第一行row[0]和第一列column[0]是否需要置0。最后利用row[0]和column[0]进行置0的操作。

2、具体思路如下：
① 我们需先判断row[0]和column[0]是否包含0，包含0的话需记录，用于后续的置0。
② 判断完row[0]和column[0]之后，遍历剩下的数据，如果matrix[i][j]==0,则将对应的row[0]和column[0]置为0。（注意这里row[0]和column[0]在初始时为0的位置还是0，注意理解这一点）
③ 之后根据row[0]和column[0]来更新数据，除第一行和第一列以外的元素。
④ 最后根据一开始row[0]和column[0]是否含0的记录，来判断是否需要将第一行和第一列置0。

3、复杂度分析
① 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数。我们至多只需要遍历该矩阵两次，（记录数据为0的行和列遍历一次，置零遍历一次）。
② 空间复杂度：空间复杂度：O(1)。我们只需要常数空间存储若干变量。

代码实现（思路一（哈希集合））：

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

void setZeroes1(vector<vector<int>>& matrix) {
	//存储需置零的行和列 
	unordered_set<int> rows,columns;
	//查找matrix[row][column]==0的元素并记录行和列 
	for(int row=0;row<matrix.size();row++){
		for(int column=0;column<matrix[0].size();column++){
			if(matrix[row][column]==0){
				rows.emplace(row);
				columns.emplace(column);
			}
		}
	}
	//如果元素的行和列在 哈希集合中存在，则需要置0 
	for(int row=0;row<matrix.size();row++){
		for(int column=0;column<matrix[0].size();column++){
			if(rows.count(row)>0||columns.count(column)>0){
				matrix[row][column]=0;
			}
		}
	}
}

int main(){
	vector<vector<int>> matrix={{1,1,1},{1,0,1},{1,1,1}};
	setZeroes1(matrix);
	for(const auto &row:matrix){
		for(const auto &num:row){
			cout<<num<<" ";
		}
		cout<<endl;
	}
	return 0;
}

代码实现（思路二（使用原二维数组记录置0信息））：

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;

void setZeroes2(vector<vector<int>>& matrix) {
	//用于记录第一行第一列是否含有0 
	bool flag_row0=false,flag_column0=false;
	
	//记录第一列是否有0 
	for(int row=0;row<matrix.size();row++){
		if(matrix[row][0]==0){
			flag_column0=true;
			break;
		}
	}
	
	//记录第一行是否有0
	for(int column=0;column<matrix[0].size();column++){
		if(matrix[0][column]==0){
			flag_row0=true;
			break;
		}
	}
	
	//记录剩余元素是否为0 ，记录在第一行和第一列 
	for(int row=1;row<matrix.size();row++){
		for(int column=1;column<matrix[0].size();column++){
			if(matrix[row][column]==0){
				matrix[0][column]=0;
				matrix[row][0]=0;
			}
		}
	}
	
	//通过第一行和第一列的记录，更新数组 
	for(int row=1;row<matrix.size();row++){
		for(int column=1;column<matrix[0].size();column++){
			if(matrix[0][column]==0||matrix[row][0]==0){
				matrix[row][column]=0;
			}
		}
	}
	//如果第一行一开始时含有0，则将第一行置为0 
	if(flag_row0){
		for(int column=0;column<matrix[0].size();column++){
			matrix[0][column]=0;
		}
	}
	//如果第一列一开始时含有0，则将第一列置为0
	if(flag_column0){
		for(int row=0;row<matrix.size();row++){
			matrix[row][0]=0;
		}
	}
}

int main(){
	vector<vector<int>> matrix={{1,1,1},{1,0,1},{1,1,1}};
	setZeroes2(matrix);
	for(const auto &row:matrix){
		for(const auto &num:row){
			cout<<num<<" ";
		}
		cout<<endl;
	}
	return 0;
}

for(const auto &str:strs)解读

//const 防止了误改操作，auto会自动匹配类型，&防止了复制使内存利用更加高效。
for(const auto &str:strs){}

unordered_map和unordered_set对比及用法请点击此链接
LeetCode 热题 100_矩阵置零(18_73)原题链接
欢迎大家和我沟通交流(✿◠‿◠)