LeetCode48

旋转图像 1. 题目描述

给定一个n×n的二维矩阵matrix表示一个图像，请你将图像顺时针旋转90°。

你必须原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例

2. 解法 2.1 转置反转解法

将一个矩阵顺时针旋转90°，其实可以先将矩阵转置，再将每一行的数组对称反转即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        //转置矩阵
        for(int i = 0; i < n; ++i)
        {
            for(int j = i; j < n; ++j)
            {
                if (i != j)
			    {
				    int temp = matrix[i][j];
				    matrix[i][j] = matrix[j][i];
				    matrix[j][i] = temp;
			    }
            }
        }
        //反转每一行
        for (int i = 0; i < n; ++i)
	    {
		    reverse(matrix[i].begin(), matrix[i].end());
	    }
    }
};

2.2 由外向内

观察变换前后的矩阵元素，可以发现，坐标为[i][j]的元素被移动到了[j][n-i-1]处。同时，[j][n-i-1]被移动到了[n-i-1][n-j-1]处，[n-i-1][n-j-1]被移动到了[n-j-1][i]处。如果i=0，j从i遍历到n-1-i，那么经过上面所说的 *** 作后就将矩阵最外圈的元素旋转了90°。之后再 *** 作内层元素即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) 
    {
        int n = matrix.size();
        if(n <= 1) return;
        for(int i = 0; i < n; ++i)
        {
            for(int j = i; j < n - 1 - i; ++j)
            {
                int 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;
            }
        }
    }
};