[坚持打卡23天]力扣leetcode面试题01.08.零矩阵

CSDN话题挑战赛第2期
参赛话题&＃xff1a;算法题解

往期打卡回顾总结&＃xff1a;

• 第一天的图的节点通路dfs、bfs&＃xff0c;顺便复习一下图的相关概念
• 第二天的模拟题&＃xff0c;重新排列单词间的空格
• 第三天快慢指针&＃xff0c;重新分组数字
• 第四天也是归纳题&＃xff0c;优美队列
• 第五天&＃xff0c;动态规划&＃xff0c;最长定差数列
• 第六天&＃xff0c;修建二叉树&＃xff0c;回顾树的遍历
• 第七天&＃xff0c;打工人&＃xff0c;k人最低成本题
• 第八天&＃xff0c;二分查找&＃xff0c;数组特征值
• 第九天&＃xff0c;贪心算法&＃xff0c;最大交换
• 第十一天&＃xff0c;真值表&＃xff0c;找规律&＃xff0c;灯泡开关
• 第十二天&＃xff0c;第一次接触扫描线&＃xff0c;覆盖面积
• 第十三天&＃xff0c;滑动窗口&＃xff0c;hash表&＃xff0c;相同字符间最长字串
• 第十五天&＃xff0c;矩阵,hash表&＃xff0c;人工岛
• 第十六天&＃xff0c;剪枝&＃xff0c;递归&＃xff0c;求k个相等子集
• 第十八天&＃xff0c;也是hash表&＃xff0c;是否能连成数组
• 第二十天&＃xff0c;三种方式、异或、求和、原地hash&＃xff0c;求消失两位数
• 第二十一天&＃xff0c;hash表、重排序&＃xff0c;字符重排
• 第二十二天&＃xff0c;字符匹配&＃xff0c;字符串轮转

题目链接与描述

编写一种算法&＃xff0c;若M × N矩阵中某个元素为0&＃xff0c;则将其所在的行与列清零。

示例 1&＃xff1a;

输入&＃xff1a;
[
[1,1,1],
[1,0,1],
[1,1,1]
]
输出&＃xff1a;
[
[1,0,1],
[0,0,0],
[1,0,1]
]
示例 2&＃xff1a;

输入&＃xff1a;
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
输出&＃xff1a;
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

关键词&＃xff1a; 标记数组

这道题&＃xff0c;标注是中等题。

1. 首先考虑存储原始0值位置后&＃xff0c;将横纵置0即可

方法一&＃xff1a;标记数组 m n

运行截图

代码

public void setZeroes(int[][] matrix) {boolean[][] zero &＃61; new boolean[matrix.length][matrix[0].length];for (int i &＃61; 0; i < matrix.length; i&＃43;&＃43;) {for (int j &＃61; 0; j < matrix[i].length; j&＃43;&＃43;) {zero[i][j] &＃61; matrix[i][j] &＃61;&＃61; 0;}}for (int i &＃61; zero.length - 1; i >&＃61; 0; i--) {for (int j &＃61; zero[i].length - 1; j >&＃61; 0; j--) {if (zero[i][j]) {setZeroesXY(matrix, i, j);}}}}private void setZeroesXY(int[][] matrix, int i, int j) {for (int i1 &＃61; matrix.length - 1; i1 >&＃61; 0; i1--) {matrix[i1][j] &＃61; 0;}for (int j1 &＃61; matrix[i].length - 1; j1 >&＃61; 0; j1--) {matrix[i][j1] &＃61; 0;}}

方法二&＃xff1a;m &＃43; n 的复杂度

和稀疏图一样&＃xff0c;我们使用m x n 的矩阵很多空间是浪费掉了&＃xff0c;我们只需要一行或者一列即可&＃xff0c;同时遍历的时候也只需要满足在行列上有0即可

运行截图

代码

public void setZeroes(int[][] matrix) {boolean[] row &＃61; new boolean[matrix.length];boolean[] col &＃61; new boolean[matrix[0].length];for (int i &＃61; 0; i < matrix.length; i&＃43;&＃43;) {for (int j &＃61; 0; j < matrix[i].length; j&＃43;&＃43;) {if (matrix[i][j] &＃61;&＃61; 0) {row[i] &＃61; col[j] &＃61; true;}}}for (int i &＃61; matrix.length - 1; i >&＃61; 0; i--) {for (int j &＃61; matrix[i].length - 1; j >&＃61; 0; j--) {if (col[j] || row[i]) {matrix[i][j] &＃61; 0;}}}}

方法三&＃xff1a; 1 的空间复杂度&＃xff1b;mn的时间复杂度

开始看题解了&＃xff0c;第一遍还没懂&＃xff0c;中等难度也可能是在这里&＃xff0c;实现出来简单&＃xff0c;要求对应时间空间复杂度的难想&＃xff1b;

思路就是利用行列都会消掉&＃xff0c;把矩阵的0位用来存储是否消除&＃xff0c;节省了m&＃43;n的空间&＃xff0c;但是需要注意如果开始0位上有0&＃xff0c;那么需要额外处理对应行列&＃xff1b;

运行截图

代码

public void setZeroes(int[][] matrix) {int n &＃61; matrix.length, m &＃61; matrix[0].length;// 起始0位是否有0boolean row0 &＃61; false;boolean col0 &＃61; false;for (int i &＃61; 0; i < n; i&＃43;&＃43;) {if (matrix[i][0] &＃61;&＃61; 0) {col0 &＃61; true;break;}}for (int j &＃61; 0; j < m; j&＃43;&＃43;) {if (matrix[0][j] &＃61;&＃61; 0) {row0 &＃61; true;break;}}// 从1位开始,归拢到0位for (int i &＃61; 1; i < n; i&＃43;&＃43;) {for (int j &＃61; 1; j < m; j&＃43;&＃43;) {if (matrix[i][j] &＃61;&＃61; 0) {matrix[0][j] &＃61; matrix[i][0] &＃61; 0;}}}// 开始遍历1判断是否需要消除for (int i &＃61; 1; i < n; i&＃43;&＃43;) {for (int j &＃61; 1; j < m; j&＃43;&＃43;) {if (matrix[0][j] &＃61;&＃61; 0 || matrix[i][0] &＃61;&＃61; 0) {matrix[i][j] &＃61; 0;}}}if (col0) {for (int i &＃61; 0; i < n; i&＃43;&＃43;) {matrix[i][0] &＃61; 0;}}if (row0) {for (int i &＃61; 0; i < m; i&＃43;&＃43;) {matrix[0][i] &＃61; 0;}}}

结尾

欢迎评论区交流&＃xff0c;每日打卡&＃xff0c;冲冲冲&＃xff01;&＃xff01;&＃xff01;