旋转图像（LeetCode 48）

恋喵大鲤鱼

发布于 2024-01-04 08:36:07

1340

发布于 2024-01-04 08:36:07

文章被收录于专栏：C/C++基础

文章目录

1.问题描述
2.难度等级
3.热门指数
4.解题思路
参考文献

1.问题描述

给定一个 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

2.难度等级

Medium。

3.热门指数

★★★★☆

4.解题思路

首先我们只能在原矩阵上进行操作，而不可以借助另一个矩阵。其次这是一个特殊的二维矩阵，列数和行数是相等的，通常称之为方阵。所以我们剩下的只需要理清楚怎么旋转90°即可。

观察上图，我们可以由外到内，一层一层地旋转。

所谓的旋转，实际上是将每一位移动到下一个位置。旋转 90° 即A[0,0]转到A[0,n]位置；A[0,n]转到A[n,n]位置；A[n,n]转到A[n,0]位置；A[n,0]转到A[0,0]位置。
上一步操作的是最外层的一层环，我们只需要一层层往里执行相同的操作，最终即可完成整个矩阵的旋转。
假设矩阵是 n*n 的，那么我们对 n/2 个环执行旋转即可完成。
对于任一层的环，假设左上角索引为[i, j]，那么 j 的终止下标为 n - i - 1。
重点来了，各个元素的交换的下标关系如下

A[i][j] 		由	A[n-j-1][i]		填充
A[n-j-1][i]		由	A[n-i-1][n-j-1]	填充
A[n-i-1][n-j-1]	由	A[j][n-i-1]		填充
A[j][n-i-1] 	由	A[i][j]   		填充

时间复杂度： O(n^2)。其中 n 是矩阵的边长。我们需要移动矩阵的所有元素，除了中间的那个元素。

空间复杂度： O(1)。为原地旋转。

下面以 Golang 为例给出实现。

func rotate(matrix [][]int) {
	n := len(matrix[0])

	// 按照层进行循环。
	for i := 0; i < n/2; i++ {
		for j := i; j < n-i-1; j++ {
			tmp := matrix[i][j]
			matrix[i][j] = matrix[n-j-1][i]
			matrix[n-j-1][i] = matrix[n-i-1][n-j-1]
			matrix[n-i-1][n-j-1] = matrix[j][n-i-1]
			matrix[j][n-i-1] = tmp
		}
	}
}

// 因为 Golang 支持多重赋值，所以交换可以写成一行。
func rotate(matrix [][]int) {
	n := len(matrix[0])
	for i := 0; i < n/2; i++ {
		for j := i; j < n-i-1; j++ {
			matrix[i][j], matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1] = matrix[n-j-1][i], matrix[n-i-1][n-j-1], matrix[j][n-i-1], matrix[i][j]
		}
	}
}