leetcode hot100 之 旋转图像

题目

给定一个n x n 的 metrix，对其进行90度的旋转。只能在原矩阵中进行操作。

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

原题链接：https://leetcode-cn.com/problems/rotate-image/

思路

因为 metrix 是一个 n x n 的结构，可以由外圈到内圈进行处理即可，圈数为 n/2，第 i 层的边长为 n - 2 * i。
旋转的过程，可以理解为，每一次将四个数依次进行位置变换，比如 1、3、9、7；2、6、8、4。转移方程为 matrix[x][y] -> matrix[y][n-1-x]
当 n 为奇数时，内圈只有一个数字，无需进行处理。

• 复杂度分析
  • 时间复杂度 O(n^2)。每个数字都会被遍历到，所以是 n^2。
  • 空间复杂度 O(1)。

代码

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int x = i;
                int y = j;
                int x_next, y_next;
                int pre = matrix[x][y];
                for (int time = 0; time < 4; time++) {
                    x_next = y;
                    y_next = n - 1 - x;
                    int temp = matrix[x_next][y_next];
                    matrix[x_next][y_next] = pre;
                    pre = temp;
                    x = x_next;
                    y = y_next;
                }
            }
        }

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24