LeetCode Hot100 矩阵专题题解
73. 矩阵置零
题目
给定一个m x n的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用原地算法。
思路
- 定义两个布尔数组，分别标记哪些行、哪些列存在0元素
- 第一次遍历矩阵，记录0所在的行和列
- 第二次遍历，只要行标记或者列标记为true，就将当前元素置0
classSolution{publicvoidsetZeroes(int[][]matrix){intm=matrix.length;// m：矩阵行数intn=matrix[0].length;// n：矩阵列数boolean[]row=newboolean[m];// row数组：标记哪一行含有0boolean[]col=newboolean[n];// col数组：标记哪一列含有0// 第一轮遍历：找到所有0，标记对应的行、列for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(matrix[i][j]==0){row[i]=col[j]=true;}}}// 第二轮遍历：根据标记置零for(inti=0;i<m;i++){for(intj=0;j<n;j++){if(row[i]||col[j]){// 当前行标记为true 或者 当前列标记为truematrix[i][j]=0;}}}}}54. 螺旋矩阵
题目
给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序，返回矩阵中的所有元素。
思路
边界收缩法，维护上下左右4个边界，按 左→右，上→下，右→左，下→上 四个方向循环遍历。
每走完一个方向收缩对应边界，每次遍历结束判断集合大小，如果收集完所有元素直接return，避免重复遍历。
classSolution{publicList<Integer>spiralOrder(int[][]matrix){introw=matrix.length;intcol=matrix[0].length;intleftLimit=0;// 左边界intupLimit=0;// 上边界intdownLimit=row-1;// 下边界intrightLimit=col-1;// 右边界List<Integer>res=newArrayList<>();while(true){// 从左向右遍历上边界for(intj=leftLimit;j<=rightLimit;j++){res.add(matrix[upLimit][j]);}upLimit++;// 上边界下移if(res.size()==row*col)returnres;// 从上向下遍历右边界for(inti=upLimit;i<=downLimit;i++){res.add(matrix[i][rightLimit]);}rightLimit--;// 右边界左移if(res.size()==row*col)returnres;// 从右向左遍历下边界for(intj=rightLimit;j>=leftLimit;j--){res.add(matrix[downLimit][j]);}downLimit--;// 下边界上移if(res.size()==row*col)returnres;// 从下向上遍历左边界for(inti=downLimit;i>=upLimit;i--){res.add(matrix[i][leftLimit]);}leftLimit++;// 左边界右移if(res.size()==row*col)returnres;}}}48. 旋转图像
题目
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。你必须在原地旋转图像。
思路
创建一个新二维数组，利用旋转公式：matrix_new[j][n-i-1] = matrix[i][j]，先把旋转结果存入新数组，最后把新数组全部复制回原矩阵。
classSolution{publicvoidrotate(int[][]matrix){intn=matrix.length;int[][]matrix_new=newint[n][n];// 辅助数组，存放旋转后的矩阵for(inti=0;i<n;i++){for(intj=0;j<n;j++){// 顺时针90度坐标映射matrix_new[j][n-i-1]=matrix[i][j];}}// 将辅助数组的值覆盖回原matrixfor(inti=0;i<n;i++){for(intj=0;j<n;j++){matrix[i][j]=matrix_new[i][j];}}}}240. 搜索二维矩阵 II
题目
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的目标值 target。
每行的元素从左到右升序排列。每列的元素从上到下升序排列。
思路
逐行遍历，对每一行使用二分查找。如果任意一行找到target，直接返回true；全部遍历完成没找到返回false。
classSolution{publicbooleansearchMatrix(int[][]matrix,inttarget){// 遍历每一行for(int[]row:matrix){intindex=search(row,target);if(index>=0){// 二分查找找到目标，返回truereturntrue;}}returnfalse;}// 单行数组二分查找，找到返回下标，找不到返回-1publicintsearch(int[]nums,inttarget){intlow=0,high=nums.length-1;while(low<=high){intmid=(high-low)/2+low;// 防止溢出的mid写法intnum=nums[mid];if(num==target){returnmid;}elseif(num>target){high=mid-1;}else{low=mid+1;}}return-1;}}小结
- 73矩阵置零：两个boolean数组标记行列0，两次遍历。
- 54螺旋矩阵：四边边界收缩，四个方向循环，收集满元素提前退出。
- 48旋转图像：辅助数组存储旋转结果，再拷贝回原数组。
- 240搜索二维矩阵II：外层循环遍历行，每行内部二分查找。
