题目:顺时针旋转矩阵

描述:有一个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)。