JAVA练习288- 旋转图像

题目概览

给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转 90 度。

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

来源：48. 旋转图像 - 力扣（LeetCode）

解题分析

方法：模拟

我们可以按照每一圈逐个处理，令当前位置为 ( i , i + x )，当前圈的边长为 n，那么可以得到每个坐标和移动的目标坐标：
( i , i + x ) → ( i + x, i + n ) → ( i + n, i + n - x ) → ( i + n - x, i )
因此只需要移动第一排，然后缩小圈，继续移动第一排直到都移动完成即可。

时间复杂度：O(n²)
空间复杂度：O(1)

class Solution { public void rotate(int[][] matrix) { int len = matrix.length; for (int i = 0; i < len; ++i) { int n = len - 2 * i; for (int x = 0; x < n-1; ++x) { rotate(matrix, i, n-1, x); } } } private void rotate(int[][] matrix, int i, int n, int x) { int temp = matrix[i+x][i+n]; matrix[i+x][i+n] = matrix[i][i+x]; int temp2 = matrix[i+n][i+n-x]; matrix[i+n][i+n-x] = temp; temp = matrix[i+n-x][i]; matrix[i+n-x][i] = temp2; matrix[i][i+x] = temp; } }