1. 矩阵置零问题解析今天要聊的是一个在算法面试中经常出现的经典题目——矩阵置零LeetCode第73题。这个问题看似简单但想要写出最优解却需要一些巧妙的思考。我第一次遇到这个问题时也是花了些时间才理解其中的精妙之处。题目要求很简单给定一个m×n的矩阵如果某个元素为0就将其所在行和列的所有元素都设为0。要求必须在原矩阵上直接修改不能使用额外的空间。这种原地修改的要求正是这个问题的挑战所在。2. 问题分析与初步解法2.1 直观解法及其局限性最直观的解法是使用两个标记数组一个记录哪些行需要置零另一个记录哪些列需要置零。具体步骤如下遍历整个矩阵记录下所有0元素所在的行和列再次遍历矩阵将标记过的行和列上的所有元素置为0这种方法的时间复杂度是O(m×n)空间复杂度是O(mn)。虽然时间复杂度已经是最优了但空间复杂度还可以进一步优化。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) rows, cols set(), set() # 第一次遍历记录0的位置 for i in range(m): for j in range(n): if matrix[i][j] 0: rows.add(i) cols.add(j) # 第二次遍历置零 for i in range(m): for j in range(n): if i in rows or j in cols: matrix[i][j] 02.2 空间复杂度优化思路为了达到O(1)的空间复杂度我们需要利用矩阵本身来存储标记信息。具体思路是使用矩阵的第一行和第一列来记录哪些行和列需要置零需要额外两个变量记录第一行和第一列本身是否需要置零这种方法巧妙地将标记信息存储在矩阵内部避免了使用额外空间。3. 最优解法实现3.1 标记策略详解最优解法的关键在于如何利用矩阵本身的空间来存储标记信息。具体步骤如下检查第一行和第一列是否有0用两个布尔变量记录遍历矩阵的其他部分如果发现0就在对应的第一行和第一列的位置标记为0根据第一行和第一列的标记将对应的行和列置零最后根据最初的布尔变量决定是否将第一行和第一列置零def setZeroes(matrix): m, n len(matrix), len(matrix[0]) 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)) # 使用第一行和第一列作为标记空间 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 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] 03.2 边界条件处理这个解法中最容易出错的地方是对第一行和第一列的处理。必须注意要先检查第一行和第一列本身是否有0并用单独的变量记录标记阶段不能修改第一行和第一列的值除了作为标记最后才根据初始记录决定是否置零第一行和第一列4. 复杂度分析与变种问题4.1 时间复杂度与空间复杂度最优解法的时间复杂度是O(m×n)因为需要遍历矩阵两次标记阶段和置零阶段。空间复杂度是O(1)只使用了常数个额外变量。4.2 相关变种问题这个问题的变种包括如果允许使用O(mn)空间但不允许使用集合数据结构如何实现如果要求只遍历矩阵一次如何实现如果矩阵非常大无法完全装入内存如何分块处理5. 实际应用场景矩阵置零算法在实际中有多种应用场景图像处理中可能需要将某些特定颜色值视为0所在的行列全部设为黑色电子表格处理中可能需要清除某些错误值所在的行列游戏开发中可能需要重置某些特殊方块所在的行列6. 常见错误与调试技巧在实现这个算法时容易犯的错误包括忘记处理第一行和第一列的特殊情况在标记阶段错误地修改了第一行或第一列的值置零阶段没有正确处理标记调试时可以打印出每次循环后的矩阵状态使用小矩阵如2×2或3×3进行测试特别注意边界条件全0矩阵、第一行有0、第一列有0等情况7. 算法优化思考虽然这个解法已经相当高效但还可以思考能否进一步减少遍历次数对于稀疏矩阵大部分元素为0是否有更优的解法如何并行化这个算法以利用多核处理器在实际面试中面试官可能会要求你逐步优化解法从最直观的方法开始一步步引导到最优解。这种展示问题解决能力的过程往往比直接写出最优解更重要。
1. 矩阵置零问题解析今天要聊的是一个在算法面试中经常出现的经典题目——矩阵置零LeetCode第73题。这个问题看似简单但想要写出最优解却需要一些巧妙的思考。我第一次遇到这个问题时也是花了些时间才理解其中的精妙之处。题目要求很简单给定一个m×n的矩阵如果某个元素为0就将其所在行和列的所有元素都设为0。要求必须在原矩阵上直接修改不能使用额外的空间。这种原地修改的要求正是这个问题的挑战所在。2. 问题分析与初步解法2.1 直观解法及其局限性最直观的解法是使用两个标记数组一个记录哪些行需要置零另一个记录哪些列需要置零。具体步骤如下遍历整个矩阵记录下所有0元素所在的行和列再次遍历矩阵将标记过的行和列上的所有元素置为0这种方法的时间复杂度是O(m×n)空间复杂度是O(mn)。虽然时间复杂度已经是最优了但空间复杂度还可以进一步优化。def setZeroes(matrix): m, n len(matrix), len(matrix[0]) rows, cols set(), set() # 第一次遍历记录0的位置 for i in range(m): for j in range(n): if matrix[i][j] 0: rows.add(i) cols.add(j) # 第二次遍历置零 for i in range(m): for j in range(n): if i in rows or j in cols: matrix[i][j] 02.2 空间复杂度优化思路为了达到O(1)的空间复杂度我们需要利用矩阵本身来存储标记信息。具体思路是使用矩阵的第一行和第一列来记录哪些行和列需要置零需要额外两个变量记录第一行和第一列本身是否需要置零这种方法巧妙地将标记信息存储在矩阵内部避免了使用额外空间。3. 最优解法实现3.1 标记策略详解最优解法的关键在于如何利用矩阵本身的空间来存储标记信息。具体步骤如下检查第一行和第一列是否有0用两个布尔变量记录遍历矩阵的其他部分如果发现0就在对应的第一行和第一列的位置标记为0根据第一行和第一列的标记将对应的行和列置零最后根据最初的布尔变量决定是否将第一行和第一列置零def setZeroes(matrix): m, n len(matrix), len(matrix[0]) 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)) # 使用第一行和第一列作为标记空间 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 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] 03.2 边界条件处理这个解法中最容易出错的地方是对第一行和第一列的处理。必须注意要先检查第一行和第一列本身是否有0并用单独的变量记录标记阶段不能修改第一行和第一列的值除了作为标记最后才根据初始记录决定是否置零第一行和第一列4. 复杂度分析与变种问题4.1 时间复杂度与空间复杂度最优解法的时间复杂度是O(m×n)因为需要遍历矩阵两次标记阶段和置零阶段。空间复杂度是O(1)只使用了常数个额外变量。4.2 相关变种问题这个问题的变种包括如果允许使用O(mn)空间但不允许使用集合数据结构如何实现如果要求只遍历矩阵一次如何实现如果矩阵非常大无法完全装入内存如何分块处理5. 实际应用场景矩阵置零算法在实际中有多种应用场景图像处理中可能需要将某些特定颜色值视为0所在的行列全部设为黑色电子表格处理中可能需要清除某些错误值所在的行列游戏开发中可能需要重置某些特殊方块所在的行列6. 常见错误与调试技巧在实现这个算法时容易犯的错误包括忘记处理第一行和第一列的特殊情况在标记阶段错误地修改了第一行或第一列的值置零阶段没有正确处理标记调试时可以打印出每次循环后的矩阵状态使用小矩阵如2×2或3×3进行测试特别注意边界条件全0矩阵、第一行有0、第一列有0等情况7. 算法优化思考虽然这个解法已经相当高效但还可以思考能否进一步减少遍历次数对于稀疏矩阵大部分元素为0是否有更优的解法如何并行化这个算法以利用多核处理器在实际面试中面试官可能会要求你逐步优化解法从最直观的方法开始一步步引导到最优解。这种展示问题解决能力的过程往往比直接写出最优解更重要。
