思路

题目分析

1. 题目给出的输入有一个N*N大小的数组，并且给出了维数N
2. 我们需要返回这个数组顺时针翻转90度后的数组

• 方法一：开辟新数组按照索引关系装填
  • 我们申请一个同样空间大小的新的二维数组ans来承接原数组mat的元素
  • 90度翻转的数组和原数组存在索引上的关系符合ans[j][n-i-1] = mat[i][j]
  • 依照这个关系双重循环即可
• 方法二：原地旋转
  • 原地我们无法直接进行旋转，因此我们要找90度前后的位置关系
  • 原数组经过水平翻转，再将对角线翻转可以得到90度的顺时针旋转
  • 依据这一规律，我们将原数组原地旋转

方法一：按照索引关系

class Solution {
public:
    vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
        // write code here
      vector<vector<int>> ans(n,vector<int>(n));	// 申请新的N*N空间
      for(int i = 0; i < n; i++){
          for(int j = 0; j < n; j++){
              ans[j][n - 1 - i] = mat[i][j];  	  // 按照索引关系重新装填
          }
      }
      return ans;
    }
};

复杂度分析

• 时间复杂度：$O\left(N^2\right)O(N^2)$O(N2)，使用了双重循环
• 空间复杂度：$O\left(N^2\right)O(N^2)$O(N2)，申请了ans的二维数组空间

方法二：原地旋转

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 - i - 1][j]);		// 水平翻转只要更改行的对称索引即可
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(mat[i][j], mat[j][i]);				// 对角线翻转只要交换行与列索引即可
            }
        }
        return mat;
    }
};

复杂度分析

• 时间复杂度：$O\left(N^2\right)O(N^2)$O(N2)，使用了双重循环
• 空间复杂度：$O\left(1\right)O(1)$O(1)，未申请额外空间