旋转图像

题意

n×n 矩阵顺时针旋转 90 度，原地修改。

思路

顺时针旋转 90° = 转置 + 每行反转。转置交换 (i,j) 和 (j,i)，然后每行反转即得顺时针旋转。也可用四元交换按层旋转。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
 * Author by Rainboy
 */
// main.cpp：先转置再每行反转 O(n²) O(1)。
#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    void rotate(vector<vector<int>> &matrix) {
        int n = matrix.size();
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                swap(matrix[i][j], matrix[j][i]);
        for (int i = 0; i < n; i++)
            reverse(matrix[i].begin(), matrix[i].end());
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<int>> a(n, vector<int>(n));
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];
    Solution().rotate(a);
    for (auto &row : a) {
        for (int x : row)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24#!/usr/bin/env python3
from typing import List


class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        for i in range(n):
            for j in range(i + 1, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        for row in matrix:
            row.reverse()


def main() -> None:
    n = int(input())
    a = [list(map(int, input().split())) for _ in range(n)]
    Solution().rotate(a)
    for row in a:
        print(*row)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：O(n²)，每个元素访问一次。
空间复杂度：O(1)。

总结

转置+反转是矩阵旋转的标准技巧。逆时针旋转 = 转置 + 每列反转。

目录

题意

思路

代码

复杂度

总结