首页 > 试题广场 >

顺时针旋转矩阵

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

热度指数：63246 时间限制：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]]

算法知识视频讲解

v_橙子

public class Solution {

public int[][] rotateMatrix(int[][] mat, int n) {

int[][] arr=new int[n][n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

arr[j][n-i-1]=mat[i][j];

}

return arr;

}

编辑于 2016-06-06 13:23:03 回复(1)

日照香炉

//就地处理,空间复杂度为O(1)，时间复杂度O(N)
class Solution {
public:
    void swap(int &a,int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
    if(n == 1 || n == 0)
    return mat;
    
    int up  = 0;
    int right = n-1;
    int down = n-1;
    int left = 0;
    
    while(up < down && left < right)
    {
        //1,2 swap
        int begin1 = up + 1;
        for(int i = left + 1;i < right;i++)
        {
            swap(mat[up][i],mat[begin1++][right]);
        }
        //2 4 swap
        begin1 = down - 1;
        for(int i = left + 1;i < right;i++)
        {
            swap(mat[up][i],mat[begin1--][left]);
        }
        //3 2 swap
        begin1 = up + 1;
        for(int i = left + 1;i < right;i++)
        {
            swap(mat[down][i],mat[begin1++][left]);
        }
        
        swap(mat[up][left],mat[up][right]);
        
        swap(mat[up][left],mat[down][left]);
        
        swap(mat[down][left],mat[down][right]);
        
        up++;
        down--;
        left++;
        right--;
    }
    return mat; 
    }
};

发表于 2016-03-13 16:35:50 回复(1)

牛客445821873号

[[1,2,3],[4,5,6],[7,8,9]],3 请问各位大佬，这种先输入矩阵元素，后输入矩阵阶数，要怎么编辑主程序里面的输入？

发表于 2022-04-24 12:38:48 回复(0)

牛客嗷嗷

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++)
            for (int j = 0; j < n / 2; j++)
                swap(mat[i][j], mat[i][n - 1 - j]);

        return mat;
    }
    static void swap(int &a, int &b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
};

发表于 2022-03-03 18:53:14 回复(0)

C++

空中转体一周半

新建一个数组，把这个数组按行导入另外一个数组的列中，只不过这个列从大到小就行了

class Solution {
public:
    vector > rotateMatrix(vector > mat, int n) {
        vector> transMat;
        vector matCol;
        for(int i=0;i<mat[0].size();++i){
            for(int i=0;i<mat.size();++i){
                matCol.push_back(0);
            }
            transMat.push_back(matCol);
            matCol.clear();
        }
        int i=0,j=0,k=n-1,l=0;
        for(;i<n;++i){
            l = 0;
            for(j=0;j<n;++j){
              transMat[l++][k]=mat[i][j];  
            }
            --k;
        }
        return transMat;
    }
};

发表于 2021-09-18 10:08:45 回复(0)

C++

猪奔

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
        for(int i = 0 ; i < n/2; i++){
            for(int j = 0 ; j  < n; j++){
                swap(mat[i][j],mat[n-1-i][j]);
            }
        }
        for(int i = 0 ; i < n;i++){
            for(int j = i + 1; j < n;j++){
                swap(mat[i][j],mat[j][i]);
            }
        }
        return mat;
    }
};

我是安徽土木学院猪贲，带你刷穿牛客

发表于 2021-08-05 14:21:52 回复(0)

Java

我想要offer~~~~

import java.util.*;

public class Solution {
    
    /*
    * 两次对折
    * ①沿着横轴进行一次对折
    * 沿着主对角线进行一次对折
    */
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        // 第一次对折
        int i = 0;
        int j = n-1;
        while(i < j){
            for(int k=0;k<n;k++){
                int tmp = mat[i][k];
                mat[i][k] = mat[j][k];
                mat[j][k] = tmp;
            }
            i++;
            j--;
        }
        // 第二次对折
        for(int k=0;k<n;k++){
            for(int m=0;m<k;m++){
                int tmp = mat[k][m];
                mat[k][m] = mat[m][k];
                mat[m][k] = tmp;
            }
        }
        return mat;
    }
}

发表于 2021-07-14 10:39:30 回复(0)

勇敢牛牛，不怕困难！

class Solution {
public:
  vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
    // transpose matrix (逆置矩阵)
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
        swap(mat[i][j], mat[j][i]);
    
    // reverse
    for (auto& row : mat)
      std::reverse(begin(row), end(row));
    
    return mat;
  }
};

发表于 2021-07-06 11:28:49 回复(0)

甲壳虫爱上了夏天

import java.util.*;

public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // 上下交换
        for(int i = 0; i <= (n - 1) / 2; i++){
            swap(mat, i, n - 1 - i);
        }
        
        // 斜对角交换
        for(int i = 0; i < n ; i++){
            for(int j = 0; j < i; j++){
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        return mat;
    }
    
    public void swap(int[][] nums, int i, int j){
        int[] temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

发表于 2021-05-17 00:08:58 回复(0)

Java

肥猿

import java.util.*;
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        // write code here
        /*
        */
        int[][] ans=new int[mat[0].length][mat.length];
        for(int i=0;i<ans.length;i++){
            for(int j=0;j<ans[0].length;j++){
                ans[i][j]=mat[ans.length-1-j][i];
            }
        }
        return ans;
    }
}

发表于 2021-03-20 13:42:44 回复(0)

C/C++

wumingde110

行变成列，列变成行

第一列从下到上变成了第一行，第二列从下到上变成了第二行，同理。。。。

class Solution {

public:
vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
// write code here
vector<vector<int> > a(n);
for(int j=0;j<n;j++)
{
for(int i=n-1;i>=0;i--)
{
a[j].push_back(mat[i][j]);
}
}
return a;
}

};

发表于 2018-08-24 10:13:49 回复(0)

听说学习能减肥

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

发表于 2018-03-23 21:46:51 回复(0)

C/C++

nbgao

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

发表于 2017-10-11 01:17:20 回复(0)

C/C++

蓝魔4

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

发表于 2017-06-16 13:45:02 回复(0)

牛客`小强

import java.util.*;

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

发表于 2017-05-18 08:42:18 回复(0)

C/C++

kelele67

//首先想到直接旋转，但是一层一层超级慢
//所以想到先沿对角线翻转，再沿水平中线翻转

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 < n -i; ++j) {
        		swap(mat[i][j], mat[n - 1 - j][n - 1 - i]);
        	}
        }
        // 沿水平中线翻转
        for (int i = 0; i < n / 2; ++i) {
        	for (int j = 0; j < n; ++j) {
        		swap(mat[i][j], mat[n - 1 - i][j]);
        	}
        }
        return mat;
    }
};

编辑于 2017-04-10 20:36:34 回复(0)

公众号:重温新知

public int[][] rotateMatrix(int[][] mat, int n) {

int[][] res = new int[n][n];

for (int i = 0; i < n; i++) {

for (int j = n - 1; j >= 0; j--) {

res[i][n-1-j] = mat[j][i];

}

return res;

发表于 2017-01-19 20:05:24 回复(0)

Java

江南消夏

新矩阵的[i][j]对应原矩阵的[n-j-1][i]

import java.util.*;

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

编辑于 2016-12-29 12:21:40 回复(0)

Java

詆調壹點

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

发表于 2016-10-18 09:45:27 回复(0)

Java

YEN-NEUer

可以在纸上画出来找规律：

B表示新的数组，A表示老的数组。

B[0][0]=A[2][0];

B[0][1]=A[1][0];

B[0][2]=A[0][0];

B[i][j]=A[n-1-j][i];

因此代码如下：

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