题目
题目形貌
给定一个 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.length
n == matrix[0].length
1 <= m, n <= 200
- 2 31 2^{31} 231 <= matrix[j] <= 2 31 2^{31} 231 - 1
题解
思绪分析
为了在不使用额外空间的情况下完成这个任务，我们可以使用矩阵的第一行和第一列来记录哪些行和列需要被置零。具体步调如下：
- 检查第一行和第一列是否有零：我们需要单独检查第一行和第一列中是否包罗零，因为稍后我们会用它们来存储其他行和列的信息。
- 标志需要置零的行和列：遍历整个矩阵，当发现某个元素为零时，将该元素地点的行的第一个元素和该元素地点的列的第一个元素设置为零。
- 根据标志置零：再次遍历矩阵（从最后一行开始，以制止覆盖第一行和第一列中的标志），如果某一行或某一列的第一个元素为零，则将整行或整列置零。
- 处理第一行和第一列：最后，根据第一步的结果决定是否需要将第一行或第一列置零。
Python 实现代码
- def setZeroes(matrix):
- m, n = len(matrix), len(matrix[0])
-
- # Step 1: Check if the first row and first column contain zeros
- first_row_has_zero = any(matrix[0][j] == 0 for j in range(n))
- first_col_has_zero = any(matrix[i][0] == 0 for i in range(m))
-
- # Step 2: Mark rows and columns that need to be zeroed
- 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
-
- # Step 3: Set matrix elements to zero based on marks
- 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
-
- # Step 4: Handle first row and column
- if first_row_has_zero:
- for j in range(n):
- matrix[0][j] = 0
- if first_col_has_zero:
- for i in range(m):
- matrix[i][0] = 0
- 检查第一行和第一列：通过 any 函数检查第一行和第一列中是否存在零，并保存结果。
- 标志需要置零的行和列：遍历矩阵，对于每个为零的元素，将其对应的行首和列首元素也设为零。
- 根据标志置零：从矩阵的最后一个元素开始向前遍历，如果某一行或某一列的标志位为零，则将该行或该列的所有元素置零。
- 处理第一行和第一列：最后根据第一步的检查结果决定是否需要将第一行或第一列置零。
这种方法确保了我们只使用常数级别的额外空间（O(1)），并且有效地完成了原地算法的要求。
提交结果
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
