Leetcode 旋转图像

地址：https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/31/

题目

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

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

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 2:

给定 matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

原地旋转输入矩阵，使其变为:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

我的解决方案

通过观察找规律会发现：

• 第i行的元素成了第n-1-i列的元素，而第j列的元素成了第i行的元素；

• 第i行的元素是由第n-1-j列的元素变换而来的，第j列的元素是由第i行的元素变换而来的。

我的思路是每遍历到一个没有转换过的元素，就一次性把与这个元素有转换关系的另外三个元素都转换完毕，例如题目示例1中遍历到第一个元素matrix[0][0]==1，就完成如下的转换：

matrix[0][0]==1  ==>>  7
matrix[2][0]==7  ==>>  9
matrix[2][2]==9  ==>>  3
matrix[0][2]==3  ==>>  1

按照这样的逻辑，就不能遍历二维矩阵的每一个元素，因为每遍历到一个元素其实相当于处理了四个元素，如果对处理过的元素再遍历一次就会再做一次转换最后得到的显然不是正确答案，并且这样的重复操作也是影响代码效率的，所以遍历的两层循环需要理解一下。在题目给的两个示例中就是：

示例1:
1: 1->3->9->7->1
2: 2->6->8->4->2

示例2:
5: 5->11->16->15->5
1: 1->10->12->13->1
9: 9->7->14->2->9
4: 4->8->6->3->4

实际转换的时候，按照上述的第二条规律逆时针方向转换，需要用一个temp来保存遍历到的matrix[i][j]。不能顺时针方向转换，因为当前元素的值已经改变，又赋给下一个对应位置元素，最后就导致对应位置上四个元素的值都是相等的，逻辑上就不对。

实现代码：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();    //n×n的二维矩阵
        for (int i = 0; i < n / 2; i++) {
            for (int j = i; j < n - 1 - i; j++) {
                int temp = matrix[i][j];   //用temp临时记录matrix[i][j]的值
                int x = i;       //用x,y表示i,j，转换过程中需要改变下标的值，而外层遍历需要保持i,j的值不变
                int y = j;
                for (int l = 1; l <= 3; l++) {   //对三个元素进行转换
                    matrix[x][y] = matrix[n - 1 - y][x];
                    int t = x;
                    x = n - 1 - y;;
                    y = t;
                }
                matrix[j][n - 1 - i] = temp;    //最后一个未转换的元素用temp赋值
            }
        }    
    }
};