48. 旋转图像

文章目录


这道题解法非常多,另外此题同 https://leetcode-cn.com/problems/rotate-matrix-lcci/ 面试题 01.07. 旋转矩阵

映射关系 AC

假设矩阵A是原本的矩阵,B是旋转后的矩阵,n是矩阵行数
那么A、B中元素有如下映射关系 A [ i ] [ j ] = B [ j ] [ n − i − 1 ] A[i][j] = B[j][n-i-1] A[i][j]=B[j][n−i−1]并且这个映射是单一映射,那现在就好办了,我们只要从A矩阵按照这个映射关系构造B矩阵就行
48. 旋转图像

由于题目要求不能用额外的空间,那么我们使用循环来完成映射,假设A是4X4的矩阵,现在 A [ 0 ] [ 0 ] A[0][0] A[0][0]需要映射
如果我们直接修改A,那么 A [ 0 ] [ 3 ] A[0][3] A[0][3]的元素会缺失,无法完成答案,所以我们需要继续执行映射,直到回到0,0本身
如此: ( 0 , 0 ) ⇒ ( 0 , 3 ) ⇒ ( 3 , 3 ) ⇒ ( 3 , 0 ) ⇒ ( 0 , 0 ) (0,0) \Rightarrow (0,3) \Rightarrow (3,3) \Rightarrow (3,0) \Rightarrow (0,0) (0,0)⇒(0,3)⇒(3,3)⇒(3,0)⇒(0,0),这个映射关系是长度为 n n n的环
如图所示

48. 旋转图像
为了描述方便,我们称上述这样的交换为循环映射

下面我们可以按照这个思路编写代码
实际上整个矩阵是被一圈一圈元素组成的,我们只需要交换每一圈的元素即可
48. 旋转图像
考虑到4X4的矩阵A,一共是由两圈元素构成
对于第一圈,我们只需要对前n - 1个元素完成循环映射即可,如图所示
48. 旋转图像
接下来我们就可以写出代码了

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        n = len(matrix)
        # 记录圈数,n==2的时候是特殊条件,只由1圈围成
        if n == 2:
            cnt = 1
        else:
            cnt = n-2 if n%2==0 else n-1
        
        # 对于矩阵的每一圈
        for i in range(cnt):
            # 每一圈最后一个元素不需要交换,同时之前交换过的元素也不需要交换
            for j in range(i,n - i - 1):
				# 起点
                sx,sy = i,j
                # 映射关系 
                nx,ny = j,n-i-1
                last = matrix[sx][sy]
                while (nx,ny) != (sx,sy):
                    matrix[nx][ny],last = last,matrix[nx][ny]
                    # 更新下一个坐标
                    nx,ny = ny,n-nx-1
                # 更新起始元素
                matrix[sx][sy] = last

这个思路很像 https://leetcode-cn.com/problems/rotate-array/ 189. 旋转数组里面的一个解法

题解

整理一下别人的题解

借用辅助空间

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // C++ 这里的 = 拷贝是值拷贝,会得到一个新的数组
        auto matrix_new = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                matrix_new[j][n - i - 1] = matrix[i][j];
            }
        }
        // 这里也是值拷贝
        matrix = matrix_new;
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

原地旋转

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 + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

和映射一样的思路,只不过这里直接写出来了

对角线反转

利用反转的性质
48. 旋转图像
48. 旋转图像
Amazing!!!

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # 水平翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
        # 主对角线翻转
        for i in range(n):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/rotate-image/solution/xuan-zhuan-tu-xiang-by-leetcode-solution-vu3m/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
上一篇:LeetCode 48.旋转图像


下一篇:48. 在类中定义装饰器