描述

题目描述

有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于300。

示例

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

知识点：矩阵，模拟
难度：⭐⭐⭐

题解

方法一：模拟

解题思路：

要达到顺时针旋转90°的效果，可以先根据左下——右上的对角线翻转，再上下翻转

算法流程：

• 如上图，可以先根据左下——右上的对角线翻转，再上下翻转
• 斜线翻转，根据对角线交换位置
• 上下翻转，交换上下元素的位置

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        if(n < 2) {
            return mat;
        }
        // 斜线翻转
        for(int i = 0; i < n; i++) {
            for(int j = i + 1; j < n; j++) {
                // 根据对角线交换位置
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        // 上下翻转
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n / 2; j++) {
                // 交换上下元素的位置
                int temp = mat[i][j];
                mat[i][j] = mat[i][n-1-j];
                mat[i][n-1-j] = temp;
            }
        }
        return mat;
    }
}

复杂度分析：

时间复杂度 O(N^2)：平均需要进行N^2次for循环，平均每个元素交换两次位置
空间复杂度 O(1)：只需要常量级别的额外空间，只是交换位置

总结：这种类似只能靠模拟、找出规律的题目，只能在纸上画出过程、得出规律，但像这种旋转90°的类型可以依靠经验

方法二：找规律

解题思路：

找出规律：mat[i][j]旋转到了mat[j][n-i-1]的位置

算法流程：

• 对每个结点按照规律进行位置填充到新的数组
• res从右到左，从上到下开始填充数据

Java 版本代码如下：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int[][] res = new int[n][n];
        // 对每个结点按照规律进行位置填充
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                // res从右到左，从上到下开始填充数据
                res[j][n - 1 - i] = mat[i][j];              
            }
        }      
        return res;  
    }
}

复杂度分析：

时间复杂度 O(N^2)：对每个结点进行选择填充
空间复杂度 O(N^2)：维护了一个二维数组用来存放结果数组

总结：画图，最容易找规律