6-1 矩阵置零 分数 10 作者 龚雄兴 单位 湖北文理学院 对于M行N的整数矩阵A,如果矩阵的某元素为零,请将它所在的行和所在的元素全部设置为零(注意:原来的零进行两个方向的传递,但新设置的零不进行二次传递)。请编写函数完成本功能(直接在原矩阵上修改),能否将空间复杂度控制在O(1)以内,即使用尽量少的辅助空间完成任务。 帮我编程实现
时间: 2024-02-19 12:02:38 浏览: 77
矩阵置零.md
好的,下面是代码实现:
```python
def setZeroes(matrix):
"""
:type matrix: List[List[int]]
:rtype: void Do not return anything, modify matrix in-place instead.
"""
m, n = len(matrix), len(matrix[0])
is_col = False
for i in range(m):
if matrix[i][0] == 0:
is_col = True
for j in range(1, n):
if matrix[i][j] == 0:
matrix[0][j] = 0
matrix[i][0] = 0
for i in range(1, m):
for j in range(1, n):
if not matrix[i][0] or not matrix[0][j]:
matrix[i][j] = 0
if matrix[0][0] == 0:
for j in range(n):
matrix[0][j] = 0
if is_col:
for i in range(m):
matrix[i][0] = 0
```
这里的思路是使用原矩阵的第一行和第一列记录该行或该列是否有零,从而将空间复杂度降至 O(1)。具体实现可以参考代码注释。
阅读全文