零售户电商网站订货网址,南宁旅游网站建设,微信建网站,长春网站建设SEO优化营销1、题目来源
73. 矩阵置零 - 力扣#xff08;LeetCode#xff09;
2、题目描述
给定一个 m x n 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例 1#xff1a; 输入#xff1a;matrix [[1,1,1],[1,0,1…1、题目来源
73. 矩阵置零 - 力扣LeetCode
2、题目描述
给定一个 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]]提示
m matrix.lengthn matrix[0].length1 m, n 200-231 matrix[i][j] 231 - 1
进阶
一个直观的解决方案是使用 O(mn) 的额外空间但这并不是一个好的解决方案。一个简单的改进方案是使用 O(m n) 的额外空间但这仍然不是最好的解决方案。你能想出一个仅使用常量空间的解决方案吗
3、题解分享
// 方法一
class Solution {public void setZeroes(int[][] matrix) {// 思路使用标记数组 定义两个数组用来标记某行或者某列是否包含0int n matrix.length;int m matrix[0].length;boolean[] rowVis new boolean[n];boolean[] colVis new boolean[m];for(int i 0;in;i){for(int j 0;jm;j){if(matrix[i][j] 0){rowVis[i] true;colVis[j] true;}}}for (int i 0; i n; i) {for (int j 0; j m; j) {if (rowVis[i] || colVis[j]) {matrix[i][j] 0;}}}}
}
//方法二
class Solution {public void setZeroes(int[][] matrix) {// 思路使用两个标记变量 实际上就是把标记数组换成matrix数组的第一行和第一列int n matrix.length;int m matrix[0].length;boolean row0 false;boolean col0 false;for(int j 0;j m ;j){if(matrix[0][j] 0){row0 true;break;}}for(int i 0;in;i){if(matrix[i][0] 0){col0 true;break;}}for(int i 0;in;i){for(int j 0;jm;j){if(matrix[i][j] 0){matrix[i][0] 0;matrix[0][j] 0;}}}for (int i 1; i n; i) {for (int j 1; j m; j) {if (matrix[i][0]0 || matrix[0][j]0) {matrix[i][j] 0;}}}if(row0){for(int j 0;jm;j){matrix[0][j] 0;}}if(col0){for(int i 0;in;i){matrix[i][0] 0;}}}
}
