题解 | #顺时针旋转矩阵#如何实现空间复杂度O（1）
顺时针旋转矩阵
http://www.nowcoder.com/practice/2e95333fbdd4451395066957e24909cc
描述
有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。
给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵。
数据范围：0 < n < 300，矩阵中的值满足 0≤val≤1000
问题分析：
首先题目的数据不是很大，所以可以通过暴力解法，也就是直接定义一个二维数组，然后按照题目要求，逐个赋值。
但是我们可不可以在原数组上进行操作呢，通过对矩阵旋转的观察可以发现起规律。
a00，a01，...，a0n
a10，a11，...，a1n
. .
. .
an0，an1，...，ann
第一行的元素跟第一列的元素交换，第一列的元素跟最后一行的元素交换，最后一行的元素和最后一列的元素交换，
最后一列的元素跟第一行的元素交换。然后逐步向内。
如何实现交换看下面代码。需要注意的是4个顶点。
复杂负分析：
时间复杂度：第一次循环的次数为n-1，后面每次循环的次数递减2，只需要进行n/2次循环。
所以整个循环次数为：n(n-1)/4，时间复杂度为O(n2).
空间复杂度：只定义了3个变量，所以空间复杂度为O(1).
class Solution {
public:
vector<vector<int> > rotateMatrix(vector<vector<int> > mat, int n) {
// write code here
if(1==n) return mat;
int ul=0,rd=n-1,tmp;//ul表示上左的起始标志，rd表示右下标志
while(ul<rd){
for(int i=ul;i<rd;++i){
tmp=mat[ul][i];//临时变量tmp保存第一个值，方便后面对各个位置赋值
//因为i是变化的且ul也是变化的，所以对其赋值就需要将这两个因素考虑进去
//如果后面不考虑ul，则会出现只有第一次循环的结果是正确的
mat[ul][i]=mat[rd+ul-i][ul];
mat[rd+ul-i][ul]=mat[rd][rd+ul-i];
mat[rd][rd+ul-i]=mat[i][rd];
mat[i][rd]=tmp;
}
++ul,--rd;
}
return mat;
}
};
投递菜鸟集团等公司6个岗位 >
查看11道真题和解析
