首页 > 代码库 > 【LeetCode】Rotate Image

【LeetCode】Rotate Image

2024-07-06 08:42:34   224人阅读

Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

 

最简单的想法，两重循环。

第一重循环是对于矩阵的层次（从外到内）

第二重循环是对于每一层次的四元素轮换

举例：

1 2 3

4 5 6

7 8 9

最外层：

1-->3-->9-->7

2-->6-->8-->4

最内层：

5

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        if(matrix.empty())
            return;
        int n = matrix.size();
        int temp;
        for(int i = 0; i < (n+1)/2; i ++)
        {
            for(int j = i; j < n-1-i; j ++)
            {
                temp = matrix[i][j];
                matrix[i][j] = matrix[n-1-j][i];
                matrix[n-1-j][i] = matrix[n-1-i][n-1-j];
                matrix[n-1-i][n-1-j] = matrix[j][n-1-i];
                matrix[j][n-1-i] = temp;
            }
        }
    }
};

 

还有一种技巧性比较强的解法。

顺时针旋转90度可以分解为两步：

1、上下颠倒reverse

2、转置transpose

举例：

1 2 3

4 5 6

7 8 9

reverse之后

7 8 9

4 5 6

1 2 3

transpose之后

7 4 1

8 5 2

9 6 3

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


联系
我们