首页R6-1 矩阵置零pta

R6-1 矩阵置零pta

时间: 2025-05-17 13:02:51 浏览: 21

### R6-1 矩阵置零 PTA 解题思路对于矩阵置零问题，在给定的一个 m×n 的矩阵中，如果某个元素为 0，则其所在的行和列中的所有元素都要被设置成 0。为了高效完成这一操作而不额外占用大量空间，可以采用一种巧妙的方法来标记哪些行列需要清零。具体来说，先遍历整个数组找到所有的零位置并记录下这些零所在的第一维索引（即行号）以及第二维索引（即列号）。但是为了避免开辟新的存储空间用于保存要清除的行与列的信息，可以直接利用原矩阵的第一行和第一列为标志位来进行标记[^1]。当遇到 matrix[i][j]==0 时： - 如果 i 不等于 0 ，则将第 j 列的第一个元素设为 0 （matrix[0][j]=0），表示该列应该全部变为 0； - 同样地，如果 j 不等于 0 ，那么也将第 i 行的第一个元素设为 0 (matrix[i][0]=0)，意味着此行需全变作 0；需要注意的是，由于可能会覆盖掉原本位于首行或首列的数据，因此还需要两个布尔变量分别用来记住原始矩阵中第一行和第一列是否有 0 存在的情况。最后再依据上述规则更新其他部分即可实现 O(1) 额外空间复杂度下的解法[^2]。下面是 Python 实现代码示例: ```python def setZeroes(matrix): is_col = False R = len(matrix) C = len(matrix[0]) for i in range(R): if matrix[i][0] == 0: is_col = True for j in range(1, C): if matrix[i][j] == 0: matrix[0][j] = 0 matrix[i][0] = 0 for i in range(1, R): for j in range(1, C): if not matrix[i][0] or not matrix[0][j]: matrix[i][j] = 0 if matrix[0][0] == 0: for j in range(C): matrix[0][j] = 0 if is_col: for i in range(R): matrix[i][0] = 0 ```

阅读全文