有个性的个人网站,为什么我的网站百度搜不到,太原再次发出通告,最优惠的建设网站建设这是一道难度为中等的题目#xff0c;让我们来看看题目描述#xff1a; 给定一个 _m_ x _n_ 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 提示#xff1a; m matrix.lengthn matrix[0].length1 m, n …这是一道难度为中等的题目让我们来看看题目描述 给定一个 _m_ x _n_ 的矩阵如果一个元素为 0 则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 提示 m matrix.lengthn matrix[0].length1 m, n 200- 2 31 2^{31} 231 matrix[i][j] 2 31 2^{31} 231 - 1 题解
class Solution {public void setZeroes(int[][] matrix) {int m matrix.length; // 获取矩阵的行数int n matrix[0].length; // 获取矩阵的列数boolean[] row new boolean[m]; // 记录需要置零的行boolean[] col new boolean[n]; // 记录需要置零的列// 第一遍遍历矩阵标记所有含有 0 的行和列for(int i 0; i m; i){for(int j 0; j n; j){if(matrix[i][j] 0){ row[i] true; // 标记该行需要置零col[j] true; // 标记该列需要置零}}}// 第二遍遍历矩阵根据标记的行和列将相应元素置零for(int i 0; i m; i){for(int j 0; j n; j){if(row[i] || col[j]){ // 如果当前行或列被标记为需要置零matrix[i][j] 0; // 置零操作}}}}
}
解题思路
1. 题目分析
给定一个 m × n 的矩阵如果某个元素为 0则需要将它所在的整行和整列的所有元素都设为 0。要求在原矩阵上直接修改不能使用额外的矩阵存储修改后的数据。
2. 解法思路 第一步标记所有需要置零的行和列 用两个数组 row[] 和 col[] 分别记录哪些行和列需要置零。 遍历矩阵如果遇到 matrix[i][j] 0就将 row[i] 和 col[j] 标记为 true表示该行或该列需要全部置零。 第二步遍历矩阵根据标记进行置零 再次遍历矩阵如果 row[i] 为 true 或 col[j] 为 true说明该位置 matrix[i][j] 需要置零。
3. 复杂度分析 时间复杂度O(m × n) 需要两次遍历整个矩阵时间复杂度为 O(m × n)符合题目要求。 空间复杂度O(m n) 额外使用了 row[] 和 col[] 两个数组空间复杂度为 O(m n)。
4. 进阶优化
如果希望减少额外空间使用可以利用矩阵的第一行和第一列来存储这些标记而不使用额外的 row[] 和 col[] 数组进而将空间复杂度优化为 O(1)。
问题与解答 [NOTE] 问题1 if(row[i] || col[j])这一句我有一点不懂为什么要么行或列被标记就会被置0呢 解答 这个 if(row[i] || col[j]) 条件的作用是如果当前元素所在的行 i 或列 j 需要置零则将该元素 matrix[i][j] 置为 0。 为什么这样判断 想象一下矩阵的置零规则 如果一个元素 matrix[i][j] 0那么它所在的整行 和 整列 都要变成 0。在第一遍遍历矩阵时我们用 row[i] 记录第 i 行是否需要全部变 0用 col[j] 记录第 j 列是否需要全部变 0。因此在第二遍遍历时 如果 row[i] true说明该行有一个元素原本是 0所以整行要变 0当前元素 matrix[i][j] 也必须变 0。如果 col[j] true说明该列有一个元素原本是 0所以整列要变 0当前元素 matrix[i][j] 也必须变 0。只要满足任意一个条件 (row[i] 或 col[j])当前元素 matrix[i][j] 必须变成 0。 举例分析 示例 1 输入矩阵 [[1, 1, 1],[1, 0, 1],[1, 1, 1]
]第一遍标记 row[] 和 col[] row [false, true, false] // 第 1 行索引 1需要置零
col [false, true, false] // 第 1 列索引 1需要置零第二遍遍历并置零应用 if(row[i] || col[j]) [[1, 0, 1], // 因为 col[1] true第二列所有元素变 0[0, 0, 0], // 因为 row[1] true整行变 0[1, 0, 1] // 因为 col[1] true第二列所有元素变 0
]总结 row[i] 记录行是否要变 0col[j] 记录列是否要变 0。if(row[i] || col[j]) 的含义是 如果这一行之前有 0则当前行的所有元素都要变 0。如果这一列之前有 0则当前列的所有元素都要变 0。如果当前行或列任意一个需要变 0那么 matrix[i][j] 也必须变 0。 这样就符合题目的要求用 两次遍历 实现 原地置零。
