Posted 2024-08-20Algorithm / C++ / job6 minutes read (About 912 words)0 visits

<Data Structures/Algorithms> leetcode hot100 - 48. Rotate Image

[LeetCode Hot 100] 48. Rotate Image

Approach 1: Rotate Layer by Layer

This problem can be tricky. Initially, it reminded me of rotating an array using multiple reversals, but it can also be rotated layer by layer with O(1) space complexity. Here’s the idea:

For a given layer, we can divide it into four edges: top, right, bottom, and left. During rotation:

Top → Right
Right → Bottom
Bottom → Left
Left → Top

If we rotate by edge, we need an O(N) array. To achieve O(1) space, rotate one element at a time and track the correspondence of positions among the four edges.

For the i-th layer from the outermost, 0 <= i < n/2 (works for odd n as the innermost element doesn’t need rotation).
For the j-th element in the current layer, 0 <= j < n - 2*i - 1 (subtract 1 to avoid over-rotating).

Top element: (i, i+j)
Right element: (i+j, n-1-i)
Bottom element: (n-1-i, n-1-i-j)
Left element: (n-1-i-j, i)

Rotation steps:

Temporarily save the left element
Move bottom → left
Move right → bottom
Move top → right
Place saved left element → top

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

Approach 2: Rotate by Flipping

Another simpler method is to rotate the matrix using flips:

Flip the matrix upside down
Flip along the main diagonal

For the main diagonal, swap matrix[i][j] with matrix[j][i]. Only swap elements in the upper triangle where i <= j (or lower triangle with j <= i).

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // Flip vertically
        for (int i = 0; i < n / 2; i++) {
            for (int j = 0; j < n; j++) {
                swap(matrix[i][j], matrix[n-1-i][j]);
            }
        }
        // Flip along main diagonal
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

中文原文

[LeetCode hot 100] 48. 旋转图像

题目链接

解法1：按圈旋转

这个题做的时候真是折磨，做的时候就想到像轮转数组那样可以通过多次翻转来实现旋转矩阵的效果，不过一想，好像可以一圈一圈转，也可以实现O(1)空间复杂度。具体是怎样转的呢？我画了一个图：

对于某一个环，可以分为上、右、下、左四条，旋转时上边转到右边，右边转到下边，下边转到左边，左边转到上边。如果以边为单位转，需要一个O(N)大小的数组来保存。想要O(1)空间复杂度可以一个一个转，只需要弄明白四条边上对应位置的关系。

我们首先用一层循环来遍历旋转的圈。假如我们在从外到内第$i$个圈，$0<i<n/2$（如果n是奇数也对，因为最内圈就一个元素不用转）。

然后用第二层循环来遍历当前轮转的是元素。假如我们在对第$j$个元素进行轮转，$0<j<n-2i-1$，注意为什么要减1，是因为每条边不能包含最后一个元素，否则就多转了一次。

上边的元素位置是：$(i,i+j)$
右边的元素位置是：$(i+j,n-1-i)$
下边的元素位置是：$(n-1-i,n-1-i-j)$
左边的元素位置是：$(n-1-i-j,i)$

所以要做的就是先把左边的元素保存一下，然后把下边放到左边，右边放到下边，上边放到右边，最后把保存的左边元素放到上边。

完整代码如下：

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

解法2：翻转实现旋转

后来看题解确实是可以用翻转实现旋转的。方法是首先对矩阵进行上下翻转，然后进行主对角线翻转，就完成了！

只需要注意主对角线两侧对称的元素关系是$matrix[i][j]$和$matrix[j][i]$，即一维下标和二维下标互换。并且上三角元素$matrix[i][j]$的下标范围是$i\leq j$，而下三角元素的下标范围是$j\leq i$

完整代码如下：

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