首页 > 试题广场 >

顺时针旋转矩阵

[编程题]顺时针旋转矩阵
  • 热度指数：63246 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

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

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

数据范围：，矩阵中的值满足

要求：空间复杂度 ，时间复杂度
进阶：空间复杂度 ，时间复杂度
示例1

输入

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

输出

[[7,4,1],[8,5,2],[9,6,3]]
算法知识视频讲解
查看答案及解析
添加回答
Java
牛客839384289号头像 牛客839384289号 
public int[][] rotateMatrix (int[][] mat, int n) {
    // write code here
    for(int i=0;i<mat.length;i++){
        for(int j=0;j<i;j++){
            int temp=mat[i][j];
            mat[i][j]=mat[j][i];
            mat[j][i]=temp;
        }
    }
    for(int i=0;i<mat.length;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;
}

发表于 2024-09-22 15:41:48 回复(0)
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头像 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头像 牛客用户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头像 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号头像 牛客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头像 哈皮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)
提交观点

问题信息

数组 基础数学
来自：面试常考算法题(一)
难度：
50条回答 37584浏览

热门推荐

通过挑战的用户

查看代码

相关试题

顺时针旋转矩阵

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号