难度: Medium
给定一个 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) 的额外空间，但这仍然不是最好的解决方案。运行时间: 52 ms
内存: 15.1 MB
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m = len(matrix)
n = len(matrix[0])
row0_flag = False
col0_flag = False
for i in range(n):
if matrix[0][i] == 0:
row0_flag = True
for i in range(m):
if matrix[i][0] == 0:
col0_flag = True
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if row0_flag:
for i in range(n):
matrix[0][i] = 0
if col0_flag:
for i in range(m):
matrix[i][0] = 0
该题解的思路是使用第一行和第一列来标记对应的行和列是否需要置零。首先，用两个变量 row0_flag 和 col0_flag 分别记录第一行和第一列是否包含 0。然后，遍历除第一行和第一列之外的所有元素，如果某个元素为 0，就将它所在行的第一个元素和所在列的第一个元素设为 0。接下来，再次遍历除第一行和第一列之外的所有元素，如果它所在行或列的第一个元素为 0，就将该元素设为 0。最后，根据 row0_flag 和 col0_flag 的值决定是否需要将第一行和第一列置零。
时间复杂度: O(mn)
空间复杂度: O(1)
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
m = len(matrix)
n = len(matrix[0])
row0_flag = False # 标记第一行是否包含 0
col0_flag = False # 标记第一列是否包含 0
# 检查第一行是否包含 0
for i in range(n):
if matrix[0][i] == 0:
row0_flag = True
# 检查第一列是否包含 0
for i in range(m):
if matrix[i][0] == 0:
col0_flag = True
# 遍历除第一行和第一列之外的所有元素，如果某个元素为 0，就将它所在行的第一个元素和所在列的第一个元素设为 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = 0
matrix[0][j] = 0
# 遍历除第一行和第一列之外的所有元素，如果它所在行或列的第一个元素为 0，就将该元素设为 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
# 如果第一行包含 0，将第一行全部置零
if row0_flag:
for i in range(n):
matrix[0][i] = 0
# 如果第一列包含 0，将第一列全部置零
if col0_flag:
for i in range(m):
matrix[i][0] = 0
使用 row0_flag 和 col0_flag 的主要原因是第一行和第一列也用作标记数组的一部分。如果在最初的遍历中直接用第一行和第一列来标记它们自己是否包含0，则后续在标记其他行和列时可能会错误地改变第一行和第一列的标记值。因此，使用单独的标记变量可以保证在处理矩阵的其他部分时，不会影响到对第一行和第一列是否包含0的正确记录。
这正是为什么要使用 row0_flag 和 col0_flag 的原因。这两个标记变量单独记录第一行和第一列是否包含0，独立于矩阵的其他部分。这样，在处理完矩阵的其他部分后，只有在这两个标记变量指示第一行或第一列包含0的情况下，才会将它们置零。这避免了因为标记其他行列时对第一行或第一列错误置零的风险。
该算法确实考虑了矩阵只有一行或一列的情况。即使矩阵只有一行或一列，使用 row0_flag 和 col0_flag 依然可以正确处理。这是因为它们将单独记录是否有元素为0，而不依赖于矩阵的其他部分。因此，该算法在处理只有一行或一列的矩阵时不需要特别调整。
在标记第一行和第一列的元素设为0时，这种操作实际上是基于矩阵中其他元素的状态。因此，只有当确定某行或某列中至少有一个元素为0时，才会将对应的第一行或第一列的元素设置为0。这种方法确保了只有那些真正需要置零的行或列被标记。此外，由于使用了 row0_flag 和 col0_flag 进行特殊的首行首列检查，所以不会影响到这两行的处理逻辑。