首页 > 试题广场 >

顺时针旋转矩阵

[编程题]顺时针旋转矩阵

热度指数：60043 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵。

数据范围： $0 < n < 300$ ，矩阵中的值满足 $0 \le val \le 1000$

要求：空间复杂度 $O(N^2)$ ，时间复杂度 $O(N^2)$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(N^2)$

示例1

输入

[[1,2,3],[4,5,6],[7,8,9]],3

输出

[[7,4,1],[8,5,2],[9,6,3]]

算法知识视频讲解

Java

神奇的安迪面试中

import java.util.*;

public class Solution {
    public int[][] rotateMatrix (int[][] mat, int n) {
        int[][] res=new int[n][n];
        for(int i=n;i>0;i--){
            for(int j=0;j<n;j++){
                res[j][n-i]=mat[i-1][j];
            }
        }
        return res;
    }
}

编辑于 2024-04-22 11:40:54 回复(0)

Java

风雨尘

public int[][] rotateMatrix (int[][] mat, int n) {
    // write code here
    int[][] res = new int[n][n];
    int index = n;
    for(int i = 0; i < mat.length; i++) {
        int[] ch = mat[i];
        res[i] = new int[n];
        for(int j = 0; j < ch.length; j++) {
            res[i][j] = mat[index-1][i];
            index --;
        }
        index = n;
    }

    return res;
}

编辑于 2024-04-15 10:46:56 回复(0)

Java

进入人才池

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here

        // 转置
        for ( int i = 0; i < n; i++ ) {
            for ( int j = i+1; j < n; j++ ) {
                swap(mat, i, j);
            }
        }

        // 反转每一行
        for ( int[] row : mat ) {
            reverse(row);
        }
        return mat;
        
    }
    void swap(int[][] nums, int i, int j) {
        nums[i][j] ^= nums[j][i];
        nums[j][i] ^= nums[i][j];
        nums[i][j] ^= nums[j][i];
    }
    void reverse(int[] nums) {
        int i = 0, j = nums.length-1;
        while ( i < j ) {
            nums[i] ^= nums[j];
            nums[j] ^= nums[i];
            nums[i] ^= nums[j];
            i++;
            j--;
        }
    }
}

发表于 2023-10-20 10:38:53 回复(0)

Java

做则必成的勇气和信心

public int[][] rotateMatrix (int[][] mat, int n) {
        // 互为转置的两个矩阵
        //遍历矩阵的下三角矩阵，和上三角矩阵位置互换
        //遍历矩阵每一行，把每一行视为一个数组，进行reverse（）
        for(int i=0;i<mat.length;i++){
            for(int j=0;j<i;j++){
                //交换上三角和下三角元素
                int tmp=mat[i][j];
                mat[i][j]=mat[j][i];
                mat[j][i]=tmp;
            }
        }
       for(int i=0;i<n;i++){//对每一行进行翻转
        reverse(mat[i]);
       }
       return mat;
    }
    public void reverse(int[] nums){
        for(int i=0;i<nums.length/2;i++){
            int tmp=nums[i];
            nums[i]=nums[nums.length-1-i];
            nums[nums.length-1-i]=tmp;
        }
    }

发表于 2023-07-29 11:14:59 回复(0)

Java

梁山教父

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        //常见栈，用来保存数组的每行元素
        Stack<ArrayList<Integer>>stack=new Stack<>();
        //每行元素入栈
        for(int i=0;i<n;i++){
            ArrayList<Integer> list=new ArrayList<>();
            for(int j=0;j<n;j++){
                list.add(mat[i][j]);
            }
            stack.push(list);
        }
        //按列遍历，从栈中取出来的这行元素就是第一列要放置的元素
        for(int i=0;i<n;i++){
            //取元素
            ArrayList<Integer> list=stack.pop();
            //遍历填充这一列
            for(int j=0;j<n;j++){
                mat[j][i]=list.get(j);
            }
        }
        return mat;
    }
}

发表于 2023-05-14 11:05:58 回复(0)

Java

勇敢牛牛不怕难

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        //每行从上到下倒转
        //再转置 a[i][j]=a[j][i]
        int h=0;
        int k=n-1;
        while(h<k){    //每行从上到下倒转
            for(int a=0;a<n;a++){
                //交换
                int temp=mat[h][a];
                mat[h][a]=mat[k][a];
                mat[k][a]=temp;
            }
            
            h++;
            k--;
        }
        //转置
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(j>=i){
                    int temp=mat[i][j];
                    mat[i][j]=mat[j][i];
                    mat[j][i]=temp;
                }
                
            }
        }
        
        return mat;
        
    }
}

发表于 2022-09-01 23:30:48 回复(0)

Java

yxjing

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int[][] res=new int[n][n];
        for(int j=0;j<=n-1;j++){
            ArrayList<Integer> path=new ArrayList<Integer>();
            for(int i=n-1;i>=0;i--){
                path.add(mat[i][j]);
            }
            int[] arr=to_arr(path);
            res[j]=arr;
        }
        return res;
    }
    public int[] to_arr(ArrayList<Integer> path){
        int len=path.size();
        int[] arr=new int[len];
        for(int i=0;i<=len-1;i++){
            arr[i]=path.get(i);
        }
        return arr;
    }
}

发表于 2022-08-26 15:36:03 回复(0)

Java

牛客用户007

第一反应这个方法，争取下次想到官方方法，hhh

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int[][] res = new int[n][n];

        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                res[i][j] = mat[n - j - 1][i];
            }
        }

        return res;
    }
}

发表于 2022-08-12 20:14:53 回复(0)

Java

万顺佑

import java.util.*;

public class Solution {
         //[[1,2,3],[4,5,6],[7,8,9]]
    public int[][] rotateMatrix(int[][] mat, int n) {
        //初步反转:[[1,4,7],[2,5,8],[3,6,9]]
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        //二次反转:[[7,4,1],[8,5,2],[9,6,3]]
        for (int i = 0; i < n; i++) {
            for (int l = 0, r = n - 1; l < r; l++, r--) {
                  int temp = mat[i][l];
                  mat[i][l] = mat[i][r];
                  mat[i][r] = temp;
            }
        }
        return mat;
    }
}

发表于 2022-08-08 15:54:23 回复(0)

Java

lizi-hust

import java.util.*;
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // 对角线交换
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int tmp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = tmp;
            }
        }
        // 水平对称交换
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n/2; j++) {
                int tmp = mat[i][j];
                mat[i][j] = mat[i][n-j-1];
                mat[i][n-j-1] = tmp;
            }
        }
        return mat;
    }
}

发表于 2022-08-07 18:45:30 回复(0)

Java

毛豆来啦

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        //创建一个新的n*n的矩阵
        int[][] newMat = new int[n][n];
        //第一行给最右一列
        //第二行给右边第二列
        for(int i = 0; i < n ;i++){
            for(int j = 0;j < n;j++){
                newMat[j][n-i-1] = mat[i][j];
            }
        }
        return newMat;
    }
}

发表于 2022-05-29 16:29:59 回复(0)

Java

每日一寄

public class Solution {
public int[][] rotateMatrix(int[][] mat, int n) {
// write code here
int res[][]=new int [n][n];
int i=0;
while (i<n){
for(int index=0;index<n;index++){
res[i][index]=mat[n-1-index][i];
}
i++;
}
return res;
}

发表于 2022-05-22 17:38:46 回复(0)

Java

牛客112285422号

//定义左上角点和右下角点（这道题因为是正方形，所以就只用了x，y和x是相等的）
//对于每对顶点，旋转他们围成的边，再聚集顶点，直到相等

//在旋转边的时候，要进行分组，再旋转，具体来讲，就是4个一组，一组一组的旋转
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int x1=0;
        int x2=mat.length-1;
        while (x1<x2)
            rotate(mat,x1++,x2--);
        return mat;
    }
    public void rotate(int[][] mat,int x1,int x2){
        //计算一共需要多少个分组，并且对每个分组进行旋转
        int groupCount=x2-x1;
        for (int i=0;i<groupCount;i++)
            rotateByGroup(mat,x1,x2,i);
    }
    
    public void rotateByGroup(int[][] mat,int x1,int x2,int i){
        //确定一个分组中的四个点，并且旋转
        int tmp1=mat[x1][x1+i];
        int tmp2=mat[x1+i][x2];
        int tmp3=mat[x2][x2-i];
        int tmp4=mat[x2-i][x1];
        mat[x1+i][x2]=tmp1;
        mat[x2][x2-i]=tmp2;
        mat[x2-i][x1]=tmp3;
        mat[x1][x1+i]=tmp4;
    }
}

发表于 2022-05-19 16:47:21 回复(0)

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++){
            int k =0;
            for(int j=n-1; j>=0;j--){
                res[i][k] = mat[j][i];
                k++;
            }
        }
        return res;
    }
}

这个思路是比较好理解的，而且比较简洁

发表于 2022-04-26 11:15:07 回复(0)

Java

老农爱编程

public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        int [][] res = new int[n][n];
        for(int j = 0 ; j < n ; j ++){
            int [] arr = new int[n];
            for(int i = n - 1;i >= 0; i --){
                arr[n - 1 - i] = mat[i][j];
            }
            res[j] = arr;
        }
        return res;
    }

发表于 2022-01-15 16:02:21 回复(0)

Java

哈皮Sun

【思路与代码】

对于空间复杂度 O(n^2)的要求，通过看旋转之后的坐标变化就可以知道其中的规律，即：

D[a,b] = D[n-1-b,a]

所以，如果空间复杂度没有严格要求，完全可以新建一个矩阵，然后把旋转之后的元素位置一一放到新矩阵中即可

具体代码如下：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        //D[a,b] = D[n-b,a]
        //空间复杂度O(n2)的解法，就是新建一个同样大小的矩阵（数组）
        int[][] res = new int[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++){
                res[i][j] = mat[n-1-j][i];
            }
        }
        return res;
    }
}

对于空间复杂度有要求的情况，需要在原数组上做更改，这就不像上面所说的只看一步的变化了，需要找出整个变化的循环规律

有兴趣的可以自己下去针对二阶、三阶、四阶矩阵找规律，现在直接给出变化规律：

temp = D[ i ] [ j ]
D[ i ] [ j ] = D[ n-1-j ] [ i ]
D[ n-1-j ] [ i ] = D[ n- 1 - i ] [ n - 1 - j ]
D[ n- 1 - i ] [ n - 1 - j ] = D[ j ] [ n - 1 - i ]
D[ j ] [ n - 1 - i ] = temp

另外，在做变换的时候，保证矩阵的左上角部分（第二象限）元素只按照上述规律变换一次即可

所以，在遍历元素的时候需要对其遍历路径进行控制

具体代码如下：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        //D[a,b] = D[n-b,a]
        //空间复杂度O(1)的解法，就是在原数组上做更改
        for(int i = 0;i < (n+1)/2;i++){
            for(int j = 0;j < n/2;j++){
                int temp = mat[i][j];
                mat[i][j] = mat[n-1-j][i];
                mat[n-1-j][i] = mat[n-1-i][n-1-j];
                mat[n-1-i][n-1-j] = mat[j][n-1-i];
                mat[j][n-1-i] = temp;
            }
        }
        return mat;
    }
}

对于矩阵的逆时针旋转，也是用同样的方法去找规律，即可解题

最后，还有一种不容易想到的方法，但是有奇效

对于矩阵的顺时针旋转，相当于将矩阵先按主对角线翻转，再左右翻转

同样的，如果是逆时针旋转，相当于将矩阵先按副对角线翻转，再左右翻转

具体代码如下：

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        //先按主对角线翻转，再左右翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int tmp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = tmp;
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n/2; j++) {
                int tmp = mat[i][(n-1) - j];
                mat[i][(n-1) - j] = mat[i][j];
                mat[i][j] = tmp;
            }
        }
        return mat;
    }
}

更多知识点可以参考博客：happysun.top。

实时更新Java、框架、数据库、数据结构与算法，希望大家一起共同进步！

发表于 2021-12-25 18:01:32 回复(0)

Java

玄鉴

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] matrix, int n) {
      if(n==0||n==1) return matrix;
      for(int i=0;i<n/2;i++){//i<m/2
          for(int j=0;j<(n+1)/2;j++){//j< (n+1)/2
     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;
          }
          }
        return matrix;
    }
}

发表于 2021-12-25 00:15:46 回复(0)

Java

YajieC

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        
        if(mat.length == 0){
            return null;
        }
        // 思路,从最后一行开始每次取出一行,从左向右一列一列的排
        int[][] returnMat = new int[mat.length][mat[0].length];
        
        for(int i = mat.length -1,lie = 0; i >= 0; i--,lie++){
            int hang = 0; // 初始化行数
            for(int j = 0; j < mat[0].length; j++){
                returnMat[hang++][lie] = mat[i][j];
            }
        }
        return returnMat;
    }
}

发表于 2021-12-17 12:30:44 回复(0)