html网站服务器搭建,百度开发者大会,正版google下载,营销型平台网站建设LeetCode 48. 旋转图像
问题描述
给定一个 n n 的二维矩阵表示图像#xff0c;要求将图像顺时针旋转 90 度。旋转必须在原地完成#xff0c;即直接修改输入矩阵#xff0c;不使用额外空间。
示例#xff1a;
输入#xff1a;matrix [[1,2,3],[4,5,6],[7,8,9]]
输出要求将图像顺时针旋转 90 度。旋转必须在原地完成即直接修改输入矩阵不使用额外空间。
示例
输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[[7,4,1],[8,5,2],[9,6,3]]解决思路转置 镜像翻转
通过两个步骤实现原地旋转
矩阵转置沿主对角线翻转元素 matrix[i][j] ↔ matrix[j][i]水平镜像翻转每行左右翻转元素 matrix[i][j] ↔ matrix[i][n-1-j]
数学证明
顺时针旋转公式matrix[i][j] → matrix[j][n-1-i]转置后matrix[i][j] → matrix[j][i]镜像翻转后matrix[j][i] → matrix[j][n-1-i] C 代码实现
class Solution {
public:void rotate(vectorvectorint matrix) {int n matrix.size();// 1. 矩阵转置 (沿主对角线翻转)for (int i 0; i n; i) {for (int j i 1; j n; j) {swap(matrix[i][j], matrix[j][i]);}}// 2. 水平镜像翻转 (每行左右翻转)for (int i 0; i n; i) {int left 0, right n - 1;while (left right) {swap(matrix[i][left], matrix[i][right]);left;--right;}}}
};关键点解析 转置操作 遍历上三角区域避免重复交换i 从 0 到 n-1j 从 i1 到 n-1交换 matrix[i][j] 和 matrix[j][i] 镜像翻转 对每行用双指针法left 和 right交换行首尾元素并向中间移动 时间复杂度O(n²) 转置O(n²/2) ≈ O(n²)镜像O(n²/2) ≈ O(n²) 空间复杂度O(1) 完全原地操作 示例推演
以 3×3 矩阵为例
初始矩阵
1 2 3
4 5 6
7 8 9步骤1转置沿主对角线翻转
1 4 7
2 5 8
3 6 9步骤2水平镜像每行左右翻转
7 4 1 ← 翻转 [1,4,7] → [7,4,1]
8 5 2 ← 翻转 [2,5,8] → [8,5,2]
9 6 3 ← 翻转 [3,6,9] → [9,6,3]最终得到顺时针旋转 90 度的结果
7 4 1
8 5 2
9 6 3此方法简洁高效严格满足原地操作要求是旋转矩阵的最优解法。
