<数据结构/算法> leetcode hot100系列. 48. 旋转图像

[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]);
            }
        }
    }
};