#P4040. 旋转图像
-
ID: 2282
Tried: 303
Accepted: 164
Difficulty: 1
旋转图像
题目描述
题目描述
给定一个 n × n 的二维矩阵 matrix，表示一个图像。请你将图像 顺时针旋转 90°。
你必须 在原地旋转图像，即直接修改输入的二维矩阵，请不要使用额外的矩阵。
输入格式
- 第一行输入整数
n，表示矩阵的大小。 - 接下来的
n行，每行输入n个整数，表示矩阵的元素。
输出格式
- 输出
n行，每行n个整数，表示旋转90°后的矩阵，数字之间用空格分隔。
输入样例 1
3
1 2 3
4 5 6
7 8 9
输出样例 1
7 4 1
8 5 2
9 6 3
输入样例 2
4
5 1 9 11
2 4 8 10
13 3 6 7
15 14 12 16
输出样例 2
15 13 2 5
14 3 4 1
12 6 8 9
16 7 10 11
题解
本题要求 原地旋转矩阵 90°，且 n 最大为 20，因此 O(n^2) 的解法是可接受的。
解法：先转置，再翻转
旋转 90° 的规律
- 先将矩阵转置（行变列，列变行）。
- 然后水平翻转（每一行左右交换）。
步骤
- 转置矩阵：
matrix[i][j]和matrix[j][i]交换。
- 水平翻转：
matrix[i][j]和matrix[i][n-j-1]交换。
示例
输入矩阵
1 2 3
4 5 6
7 8 9
第一步：转置
1 4 7
2 5 8
3 6 9
第二步：水平翻转
7 4 1
8 5 2
9 6 3
最终得到顺时针 90° 旋转 的矩阵。
时间 & 空间复杂度
- 时间复杂度：
O(n^2)（遍历两次矩阵）。 - 空间复杂度：
O(1)（原地修改，未使用额外空间）。
代码实现
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
void rotate(vector<vector<int>>& 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++) {
for (int j = 0; j < n / 2; j++) {
swap(matrix[i][j], matrix[i][n - j - 1]);
}
}
}
int main() {
int n;
cin >> n;
vector<vector<int>> matrix(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
rotate(matrix);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << matrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
Python 实现
def rotate(matrix):
"""
旋转矩阵 90°
"""
n = len(matrix)
# 1. 先转置矩阵
for i in range(n):
for j in range(i + 1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2. 再水平翻转
for i in range(n):
matrix[i].reverse() # 直接使用 reverse() 进行水平翻转
if __name__ == "__main__":
n = int(input())
matrix = [list(map(int, input().split())) for _ in range(n)]
rotate(matrix)
for row in matrix:
print(" ".join(map(str, row)))
Java 实现
import java.util.Scanner;
public class Main {
public static void rotate(int[][] matrix) {
int n = matrix.length;
// 1. 先转置矩阵
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. 再水平翻转
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = temp;
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[][] matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = scanner.nextInt();
}
}
scanner.close();
rotate(matrix);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}