矩阵专题文章目录矩阵专题73. 矩阵置零54. 螺旋矩阵法一法二48. 旋转图像法一法二240. 搜索二维矩阵 II技巧总结73. 矩阵置零73. 矩阵置零用两个标记数组分别记录每一行和每一列是否有零出现。首先遍历该数组一次如果某个元素为 0那么就将该元素所在的行和列所对应标记数组的位置置为 true最后再次遍历该数组用标记数组更新原数组classSolution{publicvoidsetZeroes(int[][]matrix){intmmatrix.length,nmatrix[0].length;boolean[]rownewboolean[m];boolean[]colnewboolean[n];for(inti0;im;i){for(intj0;jn;j){if(matrix[i][j]0){row[i]col[j]true;}}}for(inti0;im;i){for(intj0;jn;j){if(row[i]||col[j]){matrix[i][j]0;}}}}}54. 螺旋矩阵54. 螺旋矩阵法一直接模拟螺旋遍历确定四个边界实时更新边界classSolution{public:vectorintspiralOrder(vectorvectorintmatrix){vectorintres;//初始化matrix的四个边界left right top bottomintleft0,rightmatrix[0].size(),top0,bottommatrix.size();while(leftrighttopbottom){//从左到右遍历最上面一行for(intileft;iright;i){res.push_back(matrix[top][i]);}//最上面一行遍历完修改matrix的top边界top;if(topbottom){break;}//从上到下遍历最右边一列for(intjtop;jbottom;j){res.push_back(matrix[j][right-1]);}//最右边一列遍历完修改matrix的right边界--right;//如果已经遍历完matrx就结束防止matrix只有一行或只有一列走到下面逻辑重复遍历if(leftright){break;}//从右到左遍历最下面一行for(intkright-1;kleft;--k){res.push_back(matrix[bottom-1][k]);}//最下面一行遍历完修改matrix的bottom边界--bottom;if(topbottom){break;}//从下到上遍历最左边一列for(intlbottom-1;ltop;--l){res.push_back(matrix[l][left]);}left;if(leftright){break;}}returnres;}};法二找规律用DIRS数组实现上下左右转弯用n和m不断变化交换实现每个方向走几步示例 2 这 12 个数字可以分为以下 5 组1→2→3→48→1211→10→956→7其中第 1,3,5 组都是向右或者向左走的长度依次为 4,3,2这是一个从 n4 开始的逐渐递减的序列。其中第 2,4 组都是向下或者向上走的长度依次为 2,1这是一个从 m−12 开始的逐渐递减的序列。由于走的步数是有规律的我们可以精确地控制在每个方向上要走多少步无需判断是否出界、是否重复访问从 (0,−1) 开始。一开始向右走 n 步每次先走一步再把数字加入答案。走 n 步即 1→2→3→4矩阵第一排的数都加入了答案。然后向下走 m−1 步即 8→12。然后向左走 n−1 步即 11→10→9。然后向上走 m−2 步即 5。然后向右走 n−2 步即 6→7。重复上述过程直到答案的长度等于 mn。代码实现时可以这样简化代码一开始走 n 步。把 n,m 分别更新为 m−1,n这样下一轮循环又可以走 n 步相当于走了 m−1 步无需修改其他逻辑。把 n,m 分别更新为 m−1,n这样下一轮循环又可以走 n 步相当于走了 n−1 步。把 n,m 分别更新为 m−1,n这样下一轮循环又可以走 n 步相当于走了 m−2 步。依此类推每次只需把 n,m 分别更新为 m−1,n 即可。classSolution{privatestaticfinalint[][]DIRS{{0,1},{1,0},{0,-1},{-1,0}};// 右下左上publicListIntegerspiralOrder(int[][]matrix){intmmatrix.length;intnmatrix[0].length;intsizem*n;ListIntegeransnewArrayList(m*n);// 预分配空间inti0;intj-1;// 从 (0, -1) 开始for(intdi0;ans.size()size;di(di1)%4){for(intk0;kn;k){// 走 n 步注意 n 会减少iDIRS[di][0];jDIRS[di][1];// 先走一步ans.add(matrix[i][j]);// 再加入答案}inttmpn;nm-1;// 减少后面的循环次数步数mtmp;}returnans;}}48. 旋转图像48. 旋转图像法一空间复杂度O(nn)classSolution{publicvoidrotate(int[][]matrix){intnmatrix.length;int[][]matrix_newnewint[n][n];for(inti0;in;i){for(intj0;jn;j){matrix_new[j][n-i-1]matrix[i][j];}}for(inti0;in;i){for(intj0;jn;j){matrix[i][j]matrix_new[i][j];}}}}matrix_new[col][n−row−1]matrix[row][col]matrix[n−row−1][n−col−1]matrix[col][n−row−1]法二空间复杂度O(1)用一个temp保存左上的数字倒着覆盖逆时针后面的覆盖前面的最后再把temp放到指定位置四个角进行偏移继续更改剩下的外层翻转完左边界右边界–继续翻转内层的classSolution{publicvoidrotate(int[][]matrix){intleft0,rightmatrix.length-1;while(leftright){for(inti0;iright-left;i){inttopleft,bottomright;inttempmatrix[top][lefti];matrix[top][lefti]matrix[bottom-i][left];matrix[bottom-i][left]matrix[bottom][right-i];matrix[bottom][right-i]matrix[topi][right];matrix[topi][right]temp;}left;right--;}}}240. 搜索二维矩阵 II240. 搜索二维矩阵 II排除法从右上角出发向左是减小向下是增大。每次比较都能绝对排除一整行或一整列从而把时间复杂度从 O(m×n) 降维到 O(mn)classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){inti0;intjmatrix[0].length-1;while(imatrix.lengthj0){if(matrix[i][j]target){returntrue;}elseif(matrix[i][j]target){i;}else{j--;}}returnfalse;}}技巧总结在力扣 Hot 100 中矩阵题往往给人一种“全靠找规律”的错觉但实际上它们有非常固定的套路和陷阱。结合高频矩阵题的实战经验以下为核心技巧和方法核心避坑指南警惕“数据污染”这是矩阵题中最容易踩的坑。当题目要求“原地修改”矩阵时如矩阵置零绝对不能边遍历边修改原始数据。错误做法遇到 0 就立刻把整行整列置零。这会导致后续遍历分不清这个 0 是原本就有的还是你刚刚改出来的从而引发连锁错误。正确策略先标记后统一更新。第一轮遍历只记录需要置零的行和列可以额外开数组或者利用矩阵的第一行和第一列作为标记数组实现 O(1) 空间。第二轮遍历根据标记统一批量置零。遍历技巧分层/分圈处理许多矩阵问题如螺旋矩阵、旋转图像具有“由外向内”的同心矩形结构。核心思想把矩阵看作多个“图层”或“环”的嵌套一圈一圈地剥离。操作方式每一圈分别执行“从左到右、从上到下、从右到左、从下到上”四趟遍历。隐蔽坑点循环结束后矩阵不一定全部遍历完。如果行列的较小值 min(rows, cols) 是奇数剥完所有外圈后中间还会剩下一条单行或者单列需要单独处理。搜索技巧降维打击与 Z 字形消元对于搜索类矩阵题边界往往是解题的入口。全局有序如搜索二维矩阵 I矩阵展开后完全递增直接将其视为一维数组进行两次二分查找先确定行再确定列时间复杂度 O(log m log n)。局部有序如搜索二维矩阵 II行列均递增采用Z字形消元法。从右上角或左下角这个“鞍点”出发每次比较都能排除一整行或一整列将二维的乘积复杂度 O(m·n) 降维成一维的加法复杂度 O(mn)。口诀“右上角站岗哨大了左移小了下跳。”坐标变换数学规律定位对于旋转图像等问题本质上是矩阵中元素坐标的变换。不需要进行复杂的模拟直接通过分析旋转前后坐标的数学关系例如顺时针旋转 90° 的坐标变换为 (i, j) - (j, n-1-i)可以直接定位元素的新位置甚至可以通过分圈交换的方式在 O(1) 空间内完成旋转。多维动态规划DP思维演进矩阵也是多维 DP 的常见载体如不同路径、最小路径和。遇到这类题建议遵循标准的三步走思维演进暴力递归不考虑时间复杂度纯暴力枚举所有可能情况理清子问题拆分规则和递归终止条件。记忆化搜索新增一个多维缓存数组如 memo[i][j]存储已经计算过的子问题结果消除重叠子问题大幅降低时间复杂度。迭代 DP将自上而下的递归转化为自下而上的多维数组迭代推导手动控制遍历顺序如从上到下、从左到右初始化边界状态得到最终的最优解法。掌握以上五个维度的技巧基本可以覆盖 Hot 100 中绝大多数的矩阵类问题。
