传统解法
找出整体的规律，并使用一个辅助数组来存储新的矩阵。
从上图中的矩阵旋转来看：原矩阵元素的列数变成新矩阵元素的行数；原矩阵元素的行数是第2行，旋转后元素的列数是从右往左倒数第2列。因此对于原矩阵mat[i][j]，旋转后该值应该在新矩阵ans[j][n-i-1]的位置。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution {public: vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) { // write code here vector<vector<int>> ans(n,vector<int>(n)); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ans[j][n-i-1]=mat[i][j]; } } return ans; }}; |
复杂度分析：
时间复杂度：O(n^2)，矩阵元素数量n^2.
空间复杂度：O(n^2)，用一个矩阵的空间进行存储。
解法2
另外，也可以按照上面的思路，得到一个推论：矩阵经过90度顺时针旋转后，再经过每行翻转，就会得到原矩阵的转置矩阵。
那么由上面的推论：由于翻转和转置都是可逆操作(转置的转置，翻转的翻转都是自身）。我首先将矩阵转置，然后再每行翻转，就得到了顺时针旋转的矩阵。
代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution {public: vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) { //矩阵转置 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++) reverse(mat[i].begin(), mat[i].end()); return mat; }}; |
注意：其中的 swap() 函数头文件为 <iostream>, reverse()函数头文件为 <algorithm>。
解法3
当然，这道题也可以借鉴《剑指 Offer 》中顺时针打印的做法：
void ClockwiseMoseACircle(vector<vector<int> >& mat, int n, int start);
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param mat int整型vector<vector<>>
* @param n int整型
* @return int整型vector<vector<>>
*/
vector<vector<int> > rotateMatrix(vector<vector<int> >& mat, int n) {
// write code here
//总共需要旋转多少圈
int leftn = n;
int start = 0;
while(leftn>0)
{
for(int i=0; i<leftn-1; i++)
{
ClockwiseMoseACircle(mat, n, start);
}
leftn -= 2;
start++;
}
return mat;
}
};
//思路：先搞出来一圈，将一圈逆时针地置数
//start = 0; endX=n-1-start; endY=n-1-start;
void ClockwiseMoseACircle(vector<vector<int> >& mat, int n, int start)
{
int end = n-1-start;
if(start == end)
{
return;
}
int leave = mat[start][start];
//第一步：对于start 所在的列
for(int i=start; i<end; i++)
{
mat[i][start] = mat[i+1][start];
}
//第二步：对于end所在的行
for(int i=start; i<end; i++)
{
mat[end][i] = mat[end][i+1];
}
//第三步：对于end所在的列
for(int i=end; i>start; i--)
{
mat[i][end] = mat[i-1][end];
}
//第四步：对于start 所在的行
for(int i=end; i>start; i--)
{
if(i==start+1)
{
mat[start][i] = leave;
}
else {
mat[start][i] = mat[start][i-1];
}
}
}