题目：顺时针旋转矩阵

描述：有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。

示例1：输入：[[1,2,3],[4,5,6],[7,8,9]],3，返回值：[[7,4,1],[8,5,2],[9,6,3]]


解法一：

思路分析：通读题目，我们发现将N*N的矩阵顺时针旋转90度，相当于将其重新进行排列，可以直接采用暴力法进行破解求解，直接使用swap()函数，先进行对角线的交换，再翻转即可得到最终答案。

实例分析：[[1,2,3],[4,5,6],[7,8,9]],3
矩阵刚开始为：

1

2

3

4

5

6

7

8

9


先沿着左对角线做翻转为：

1

4

7

2

5

8

3

6

9


输出为：[[1,4,7],[2,5,8],[3,6,9]]

再将元素进行翻转得到[[7,4,1],[8,5,2],[9,6,3]]。

最终将矩阵顺时针旋转90度后结果变为：

7

4

1

8

5

2

9

6

3


我们通过分析可知，就是将第一行与第一列做了交换，将第一列的值赋给第一行，第二列给了第二行，第三列给了第三行，就是将矩阵顺时针旋转90度。

这道题和大学中的学到的线性代数中的转置矩阵如出一辙，不同的是第一行转置到最后一列了。

具体C++代码如下：  
class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
        for (int i=0;i<n;++i){
            for (int j=0;j<i;++j){
                swap(mat[i][j],mat[j][i]);//先交换
            }
        }
        for (int i=0;i<n;++i)
            reverse(mat[i].begin(),mat[i].end());//再将内部元素翻转
        return mat;
    }
};

因为采用了暴力法，所以其时间复杂度为O(N^2)，没有占用任何存储空间，所以其空间复杂度为O(1)。

 

解法二：

思路分析：我们也可以直接进行求解，新建一个一模一样的temp矩阵对象，通过解法一观察，我们发现主要要循环的将mat[i][j]旋转到mat[j][n-i-1]的位置，即可得到最终旋转90度的结果。

具体java代码如下所示： 


import java.util.*;
 
public class Rotate {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int[][] temp = new int[n][n];//新建temp对象，作为最终返回的对象
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                temp[j][n-1-i] = mat[i][j];//直接交换
            }
        }
        return temp;
    }
}


两个for循环逐个进行判断，所以其时间复杂度为O(N^2)，因为创建了一个新的二维数组的空间，所以其空间复杂度为O(N^2)。