1. 矩阵问题实战从力扣73到74题的解题思路作为一名经常刷题的开发者我发现在处理二维矩阵问题时很多初学者容易陷入暴力解法的泥潭。今天我想分享两道经典的矩阵题目——力扣第73题《矩阵置零》和第74题《搜索二维矩阵》的解题笔记。这两道题看似简单但其中蕴含着对矩阵遍历、空间优化和二分查找的深刻理解。2. 力扣73题矩阵置零的三种解法2.1 问题描述与暴力解法给定一个m×n的矩阵如果一个元素为0则将其所在行和列的所有元素都设为0。要求使用原地算法。最直观的想法是遍历矩阵遇到0就把对应的行和列标记下来最后统一置零。但这样需要额外的O(mn)空间存储标记。在实际面试中面试官通常会要求我们优化空间复杂度。def setZeroes(matrix): rows set() cols set() m, n len(matrix), len(matrix[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)。具体步骤先检查第一行和第一列是否需要置零用第一行和第一列作为标记数组根据标记置零内部元素最后处理第一行和第一列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] 0注意这种方法虽然节省了空间但会修改原始矩阵的第一行和第一列在实际工程中需要评估是否可接受。2.3 位运算极致优化对于极致的空间优化可以使用位运算来标记需要置零的行列。这种方法适用于矩阵规模不是特别大的情况比如m,n ≤ 64因为我们需要用两个64位整数来存储标记。def setZeroes(matrix): row_mask 0 col_mask 0 m, n len(matrix), len(matrix[0]) for i in range(m): for j in range(n): if matrix[i][j] 0: row_mask | 1 i col_mask | 1 j for i in range(m): for j in range(n): if (row_mask (1 i)) or (col_mask (1 j)): matrix[i][j] 03. 力扣74题搜索二维矩阵的三种解法3.1 问题描述与暴力解法编写一个高效的算法来判断m×n矩阵中是否存在一个目标值。该矩阵具有如下特性每行中的整数从左到右按升序排列每行的第一个整数大于前一行的最后一个整数最直接的方法是线性扫描整个矩阵时间复杂度O(mn)。但显然没有利用矩阵的有序特性。3.2 二分查找法由于矩阵整体有序我们可以将其视为一个展开的一维数组进行二分查找。关键在于如何将一维索引转换为二维坐标def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) left, right 0, m * n - 1 while left right: mid (left right) // 2 row mid // n col mid % n if matrix[row][col] target: return True elif matrix[row][col] target: left mid 1 else: right mid - 1 return False这种解法的时间复杂度是O(log(mn))空间复杂度O(1)是最优解之一。3.3 行列双指针法另一种思路是从矩阵的右上角开始搜索如果当前元素等于目标值返回true如果当前元素大于目标值向左移动一列如果当前元素小于目标值向下移动一行def searchMatrix(matrix, target): if not matrix or not matrix[0]: return False m, n len(matrix), len(matrix[0]) row, col 0, n - 1 while row m and col 0: if matrix[row][col] target: return True elif matrix[row][col] target: col - 1 else: row 1 return False这种方法的时间复杂度是O(mn)虽然不如二分查找高效但在某些特殊情况下可能更有优势。4. 矩阵问题常见陷阱与优化技巧4.1 边界条件处理在处理矩阵问题时特别容易忽略边界条件。比如空矩阵或单行/单列矩阵矩阵元素全为0或全为1的特殊情况矩阵只有一行或一列需要置零的情况4.2 空间复杂度优化思路当题目要求原地操作时考虑能否利用输入数据本身存储中间状态能否用位运算压缩存储标记信息能否通过多次遍历分离标记和应用阶段4.3 时间复杂度优化思路对于搜索类问题利用数据有序特性优先考虑二分查找从特殊位置如对角线、右上角开始搜索分治思想将大矩阵分解为小矩阵处理5. 矩阵问题的扩展练习为了巩固矩阵处理能力建议尝试以下力扣题目旋转图像螺旋矩阵搜索二维矩阵 II有序矩阵中第K小的元素重塑矩阵每道题都有其独特的解题技巧多练习才能培养矩阵问题的直觉。我在最初刷题时专门用一周时间集中攻克矩阵相关问题效果非常显著。