矩阵置零
使用标记数组
-
解题思路：
- 定义两个标记数组，分别记录每一行和每一列是否有零出现；
- 遍历该二维数组一次，如果某个元素为 0；
- 那么就将该元素所在的行和列所对应标记数组的位置置为 true；
- 最后再次遍历该数组，用标记数组更新原数组即可；
- 定义两个标记数组，分别记录每一行和每一列是否有零出现；
-
复杂度：
- 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数；
- 空间复杂度：O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数，分别记录每一行或每一列是否有零出现；
-
代码实现：
var setZeroes = function (matrix) { const m = matrix.length, n = matrix[0].length; // 记录 行、列 为 0 的位置 const row = new Array(m).fill(false); const col = new Array(n).fill(false); // 记录 0 的位置，更新到 row、col 数组中 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (matrix[i][j] === 0) { row[i] = col[j] = true; } } } // 根据 row、col 标记的位置，更新原数组 for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { if (row[i] || col[j]) { matrix[i][j] = 0; } } } };
使用两个标记变量
-
解题思路：
- 用矩阵的第一行和第一列作为两个标记数组，以达到 O(1) 的额外空间；
- 但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0，因此需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0；
- 根据标记更新矩阵；
- 最后使用两个标记变量更新第一行与第一列即可；
-
复杂度：
- 时间复杂度：O(mn)，其中 m 是矩阵的行数，n 是矩阵的列数；
- 空间复杂度：O(1)，只需要常数空间存储若干变量；
-
代码实现：
var setZeroes = function (matrix) { const m = matrix.length, n = matrix[0].length; // 标记 第一行、第一列是否有 0 let flagCol0 = false, flagRow0 = false; // 遍历第一行，是否有 0 for (let i = 0; i < m; i++) { if (matrix[i][0] === 0) { flagCol0 = true; } } // 遍历第一列，是否有 0 for (let j = 0; j < n; j++) { if (matrix[0][j] === 0) { flagRow0 = true; } } // 标记：遇到 0，则将 第一行、第一列 对应索引都置 0 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (matrix[i][j] === 0) { matrix[i][0] = matrix[0][j] = 0; } } } // 根据标记 0的位置，覆盖数组 for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { if (matrix[i][0] === 0 || matrix[0][j] === 0) { matrix[i][j] = 0; } } } // 如果第一列、第一行原来有 0，则将第一行、第一列全部置 0 if (flagCol0) { for (let i = 0; i < m; i++) { matrix[i][0] = 0; } } if (flagRow0) { for (let j = 0; j < n; j++) { matrix[0][j] = 0; } } };
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1047. 删除字符串中的所有相邻重复项
上一篇
评论
