当前位置：首页 > news >正文

leetcode二维数组高频面试题详解：48.原地旋转矩阵 + 240.杨氏矩阵查找算法深度剖析

news 2026/6/5 18:01:32

🔥你好我是fengxin_rou这是我的个人主页fengxin_rou的主页

❄️欢迎查看我的专栏我的专栏

《Java后端学习》、《JAVASE基础》、《JUC并发》、《redis》、《JVM虚拟机》、《MYSQL》、《黑马点评》、《rabbitmq》、《JavaWeb+AI的talis学习系统》、《苍穹外卖》

一、前言

二、LeetCode48 旋转图像：n×n 方阵原地顺时针旋转 90° 详解

2.1 题目需求与核心难点

2.1.1 原题题意回顾

2.1.2 解题核心难点

2.2 数学坐标变换原理推导

2.2.1 循环边界推导（关键易错点）

2.3 Java 完整可运行代码实现

2.4 第二种解题思路：两次翻转（上下翻转 + 主对角线翻转）拓展方案

2.5 踩坑总结与面试易错点

2.6 拓展延伸：逆时针旋转 90° 变形题思路

三、LeetCode240 搜索二维矩阵 II：杨氏矩阵高效查找算法详解

3.1 题目特性与题意分析

3.1.1 矩阵两大关键有序属性

3.1.2 最优算法切入点：选左下角 / 右上角作为起始坐标

3.2 贪心查找算法原理拆解

3.3 Java 完整 AC 代码实现

3.4 其他解法拓展：逐行二分查找（进阶对比）

3.5 高频踩坑点汇总

3.6 面试拓展提问

四、两道题目面试横向对比总结

五、算法学习优化拓展与资源推荐

六、结语

一、前言

在 Java 后端、算法面试当中，二维矩阵操作是笔试与现场面试高频考点，其中 LeetCode 第 48 题《旋转图像（原地顺时针 90° 旋转 n 阶方阵）》、LeetCode 第 240 题《搜索二维矩阵 II（杨氏矩阵查找）》是大厂算法题库经典标杆题目。两道题目分别考察矩阵坐标变换数学规律与有序数组的二分思想 + 贪心查找，也是数组进阶学习绕不开的核心例题。

本文将从原理推导、解题思路、代码落地、易错踩坑、多种优化方案五个维度，完整拆解两道经典算法题，全部代码基于 Java 实现，可直接粘贴至 LeetCode 在线 OJ 运行通过。

二、LeetCode48 旋转图像：n×n 方阵原地顺时针旋转 90° 详解

2.1 题目需求与核心难点

2.1.1 原题题意回顾

给定大小为n×n的二维整数矩阵，要求原地顺时针旋转 90 度，不允许开辟额外同等大小数组存储结果，只能在原输入矩阵上直接修改元素，空间复杂度约束为\(O(1)\)。示例输入 3 阶方阵：

1 2 3 4 5 6 7 8 9

顺时针旋转 90° 后输出：

7 4 1 8 5 2 9 6 3

2.1.2 解题核心难点

常规思路：新建数组按映射关系赋值，时间\(O(n^2)\)、空间\(O(n^2)\)，违反原地修改的题目硬性限制；难点 1：推导顺时针 90° 旋转时四个对应位置的坐标数学变换公式；难点 2：确定双重循环的遍历边界，避免同一个元素被多次轮换、重复修改导致数据错乱；难点 3：区分奇数阶、偶数阶方阵中心元素处理逻辑（奇数阶矩阵正中心元素旋转后位置不变，无需参与交换）。

2.2 数学坐标变换原理推导

设原矩阵下标[i,j]（行 i，列 j，数组下标从 0 开始，矩阵边长 n），顺时针旋转 90° 后，元素会轮换到四个点位：

2.2.1 循环边界推导（关键易错点）

外层循环行i：只需要遍历上半部分行i < n/2，下半行会被上层元素轮换覆盖，重复遍历会二次修改；
内层循环列j：奇数阶矩阵中间列不需要遍历，因此j < (n+1)/2，兼容奇偶两种阶数：
- n 为偶数：\(n=4，(4+1)/2=2\)，j<2，前两列遍历；
- n 为奇数：\(n=3，(3+1)/2=2\)，j<2，前两列遍历，中间列 j=2 跳过（中心元素不动）。

2.3 Java 完整可运行代码实现

class Solution { public void rotate(int[][] matrix) { // 获取方阵阶数n int n = matrix.length; // 外层：行边界 i < n/2 for(int i = 0; i < n / 2; i++){ // 内层：列边界 j < (n+1)/2，兼容奇偶阶矩阵 for(int j = 0; j < (n+1) / 2; j++){ // 暂存左上角起始元素 int temp = matrix[i][j]; // 四个点位循环赋值轮换 matrix[i][j] = matrix[n-1-j][i]; matrix[n-1-j][i] = matrix[n-1-i][n-1-j]; matrix[n-1-i][n-1-j] = matrix[j][n-1-i]; matrix[j][n-1-i] = temp; } } } }

代码说明：时间复杂度\(O(n^2)\)（每个元素仅被访问 1 次），空间复杂度\(O(1)\)，仅使用单个临时变量 temp，完全满足原地修改要求，LeetCode 提交可全用例 AC。

2.4 第二种解题思路：两次翻转（上下翻转 + 主对角线翻转）拓展方案

除四点轮换法外，业界通用另一种原地旋转思路：先上下翻转整行，再沿主对角线翻转，同样满足(O(1))原地要求，附上拓展代码：

class SolutionRotate2 { public void rotate(int[][] matrix) { int n = matrix.length; // 第一步：上下行翻转 for(int i = 0; i < n/2; i++){ int[] temp = matrix[i]; matrix[i] = matrix[n-1-i]; matrix[n-1-i] = temp; } // 第二步：主对角线(i==j)两侧元素互换 for(int i = 0; i < n; i++){ for(int j = i+1; j < n; j++){ int temp = matrix[i][j]; matrix[i][j] = matrix[j][i]; matrix[j][i] = temp; } } } }

2.5 踩坑总结与面试易错点

循环边界写错：若内层 j 写成j<n/2，奇数矩阵中间列元素无法参与轮换，结果错误；
赋值顺序颠倒：四个点位赋值必须倒序，先存起点值，从后往前覆盖，顺序错误直接数据错乱；
误区：新手容易直接开辟新数组存储结果，虽然逻辑简单，但违背题目原地核心约束，面试直接扣分；

2.6 拓展延伸：逆时针旋转 90° 变形题思路

逆时针 90° 可修改坐标映射公式，或调整翻转顺序（左右翻转 + 对角线翻转），面试常由原题变形提问。

三、LeetCode240 搜索二维矩阵 II：杨氏矩阵高效查找算法详解

3.1 题目特性与题意分析

3.1.1 矩阵两大关键有序属性

每行元素：从左到右严格升序；
每列元素：从上到下严格升序；该类有序矩阵也被称作杨氏矩阵（Young tableau），要求在\(O(m+n)\)最优时间复杂度内查找目标 target，禁止暴力全遍历\(O(mn)\)。样例矩阵：

1 4 7 11 15 2 5 8 12 19 3 6 9 16 22 10 13 14 17 24

查找 target=5 返回 true，查找 target=20 返回 false。【此处插入杨氏矩阵查找起点（左下角）标注示意图，箭头标注移动规则】

3.1.2 最优算法切入点：选左下角 / 右上角作为起始坐标

左下角特点：本行最大、本列最小；
- 当前值 < target：本列全部小于 target，列右移j++；
- 当前值 > target：本行全部大于 target，行上移i--；
同理右上角（本行最小、本列最大）也可作为起点，移动逻辑反向。

3.2 贪心查找算法原理拆解

起始坐标：i = m-1（最后一行下标），j=0（首列下标），循环终止条件：行越上界 (i<0) 或列越右界 (j>= 总列数)：

matrix[i][j] < target：当前整列所有元素≤当前值，目标不可能在本列，列 + 1；
matrix[i][j] > target：当前整行所有元素≥当前值，目标不可能在本行，行 - 1；
相等直接返回 true；循环结束未命中返回 false。

3.3 Java 完整 AC 代码实现

class Solution { public boolean searchMatrix(int[][] matrix, int target) { // 边界特判：空矩阵直接返回false if(matrix == null || matrix.length == 0 || matrix[0].length == 0){ return false; } // 起点：左下角坐标，最后一行、第0列 int i = matrix.length - 1; int j = 0; // 循环：坐标不出矩阵边界 while(i >= 0 && j < matrix[0].length){ if(matrix[i][j] < target){ // 偏小→右移一列 j++; }else if(matrix[i][j] > target){ // 偏大→上移一行 i--; }else{ // 找到目标值 return true; } } // 遍历结束未找到 return false; } }

复杂度：时间\(O(m+n)\)（行、列最多各走一次），空间\(O(1)\)，最优解，LeetCode 全部测试用例通过。

3.4 其他解法拓展：逐行二分查找（进阶对比）

由于每行有序，可对每行单独二分查找，时间复杂度\(O(m*logn)\)，数据量极大时效率低于贪心\(O(m+n)\)，附上二分版本代码：

class SolutionSearchBinary { public boolean searchMatrix(int[][] matrix, int target) { for(int[] row : matrix){ // 单行二分 int left = 0, right = row.length -1; while(left <= right){ int mid = left + (right - left)/2; if(row[mid] == target) return true; else if(row[mid] < target) left = mid +1; else right = mid -1; } } return false; } }

3.5 高频踩坑点汇总

空数组边界遗漏：未判断matrix[0].length==0，输入空行数组会触发数组下标越界异常；
起始坐标选错：从左上角 (0,0) 开始无法贪心移动，只能暴力遍历，算法直接退化；
移动方向搞反：小于 target 时错误行下移，大于 target 错误列左移，逻辑完全失效。

3.6 面试拓展提问

面试官延伸：杨氏矩阵查找第 K 小元素，基于本题思路衍生堆解法，是进阶面试考点。

四、两道题目面试横向对比总结

题目	核心思想	最优时空复杂度	考察侧重点
48. 旋转矩阵	坐标数学变换 / 矩阵翻转	\(O(n^2)、O(1)\)	二维数组下标规律、原地操作思维
240. 杨氏查找	贪心 + 有序特性	\(O(m+n)、O(1)\)	有序数据的贪心策略、边界处理

【此处插入两张题目考点思维导图汇总图片占位】

五、算法学习优化拓展与资源推荐

刷题平台官方文档LeetCode 官方中文题库文档：https://leetcode.cn/problemset/all/，可在线调试两道原题，查看官方题解与多语言实现方案；
算法开源仓库Java 算法刷题开源库（Github）：https://github.com/doocs/leetcode，收录全 LeetCode 题解、多思路优化版本，适合日常查漏补缺。