😎 作者介绍:我是程序员行者孙,一个热爱分享技术的制能工人。计算机本硕,人工制能研究生。公众号:AI Sun,视频号:AI-行者Sun
🎈 本文专栏:本文收录于《深入浅出算法》系列专栏,相信一份耕耘一份收获,我会系统全面的分享算法课程,届时可以拳打字节,脚踢腾讯
🤓 欢迎大家关注其他专栏,我将分享Web前后端开发、人工智能、机器学习、深度学习从0到1系列文章。
🖥 随时欢迎您跟我沟通,一起交流,一起成长、进步!
给定一个
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 = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出:[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
正常思路不难,思路二三怎么说呢,有点shi山换空间的感觉,代码可读性太差了(上班这么写就等着挨骂),但是想法值得借鉴
思路 1:两次遍历
- 记录信息:首先遍历矩阵,记录下所有为0的元素的行列索引。你可以使用两个哈希表或数组来记录这些信息,一个用于行,一个用于列。
- 标记行和列:创建两个布尔数组(或者在原矩阵中使用额外的一行和一列作为标记),用来标记哪些行和列应该被置零。
- 置零操作:再次遍历矩阵,根据标记数组,将所有应该置零的行和列的元素都设置为0。
代码:
class Solution {
public:
// setZeroes函数用于将矩阵中的所有0元素所在行和列置零
void setZeroes(vector<vector<int>>& matrix) {
// 获取矩阵的行数和列数
int n = matrix.size(), m = matrix[0].size();
// 初始化行和列的状态数组,用于标记哪些行和列需要置零
vector<int> row(n, false), col(m, false);
// 第一次遍历,标记需要置零的行和列
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// 如果当前元素为0,则标记对应行和列
if(matrix[i][j] == 0) {
row[i] = true; // 标记第i行需要置零
col[j] = true; // 标记第j列需要置零
}
}
}
// 第二次遍历,根据标记结果将矩阵中对应位置的元素置零
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
// 如果当前行或列被标记,则将元素置零
if(row[i] || col[j]) {
matrix[i][j] = 0;
}
}
}
}
};
思路 2:一次遍历 + 行/列操作
- 标记行和列:在一次遍历中,当遇到一个为0的元素时,立即标记对应的行和列。这可以通过在行和列的首尾元素中设置一个标记值来实现(例如,将行的第一个元素和列的最后一个元素设为一个特定的非零值,如-1)。
- 置零操作:在完成标记后,再次遍历矩阵,根据标记值来将整行或整列置零。
代码:
class Solution {
public:
// setZeroes函数用于将矩阵中的所有0元素所在行和列置零
void setZeroes(vector<vector<int>>& matrix) {
// 获取矩阵的行数m和列数n
int m = matrix.size();
int n = matrix[0].size();
// 标记第一行和第一列是否包含0
int flag_col0 = false, flag_row0 = false;
// 遍历第一行和第一列,如果发现0,则设置相应的标记为true
for (int i = 0; i < m; i++) {
if (!matrix[i][0]) { // 如果第一列的某个元素为0
flag_col0 = true;
}
}
for (int j = 0; j < n; j++) {
if (!matrix[0][j]) { // 如果第一行的某个元素为0
flag_row0 = true;
}
}
// 遍历矩阵的剩余部分(排除第一行和第一列)
// 如果发现0,将对应的第一行和第一列的元素置零
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (!matrix[i][j]) { // 这里用!表示检查是否为0
matrix[i][0] = 0; // 将第一列对应的元素置零
matrix[0][j] = 0; // 将第一行对应的元素置零
}
}
}
// 再次遍历矩阵的剩余部分,将之前标记为0的元素实际置零
// 这里利用了第一行和第一列已经更新的事实
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (!matrix[i][0] || !matrix[0][j]) { // 检查第一行或第一列的对应元素是否为0
matrix[i][j] = 0; // 将当前元素置零
}
}
}
// 最后,根据之前的标记,将第一行和第一列的所有元素置零
// 这一步是必要的,因为第一行和第一列的元素可能在之前的遍历中没有被检查
if (flag_col0) {
for (int i = 0; i < m; i++) {
matrix[i][0] = 0; // 如果第一列有0,将第一列所有元素置零
}
}
if (flag_row0) {
for (int j = 0; j < n; j++) {
matrix[0][j] = 0; // 如果第一行有0,将第一行所有元素置零
}
}
}
};
思路 3:原地标记 + 矩阵重构
- 原地标记:遍历矩阵,对于每个元素,如果它为0,则直接将其所在行和列的其他元素也设置为0。
- 矩阵重构:在完成置零操作后,遍历矩阵,对于每个元素,如果它不在原地被置零(即它不在标记的行或列中),则将其复制到一个新的矩阵中,从而得到最终的结果。
class Solution {
public:
// setZeroes函数用于将矩阵中的所有0元素所在行和列置零
void setZeroes(vector<vector<int>>& matrix) {
// 获取矩阵的行数m和列数n
int m = matrix.size();
int n = matrix[0].size();
// flag_col0用于标记第一列中是否存在0
int flag_col0 = false;
// 遍历矩阵的每一行
for (int i = 0; i < m; i++) {
// 如果第一行的某个元素为0,则将flag_col0设置为true
if (!matrix[i][0]) {
flag_col0 = true;
}
// 遍历矩阵的每一列,跳过第一列
for (int j = 1; j < n; j++) {
// 如果当前元素为0,则将对应行的第一列元素和对应列的第一行元素设置为0
if (!matrix[i][j]) {
matrix[i][0] = 0; // 将当前行的第一列元素置零
matrix[0][j] = 0; // 将当前列的第一行元素置零
}
}
}
// 从矩阵的底部开始向上遍历
for (int i = m - 1; i >= 0; i--) {
// 遍历矩阵的每一列,跳过第一列
for (int j = 1; j < n; j++) {
// 如果当前行的第一列元素或当前列的第一行元素已置零,则将当前元素置零
if (!matrix[i][0] || !matrix[0][j]) {
matrix[i][j] = 0;
}
}
// 如果第一列中存在0,且当前行是第一行,则将第一列的当前行元素置零
if (flag_col0) {
matrix[i][0] = 0;
}
}
}
};
版权声明:本文为博主作者:程序员行者孙原创文章,版权归属原作者,如果侵权,请联系我们删除!