学步园

一张图像表示成n X n的矩阵，写一个函数把图像左旋转90度。不开辟额外的存储空间

我们假设要将图像逆时针旋转90度。原图如下所示：
                1 2 3 4 
                5 6 7 8 
                9 10 11 12 
               13 14 15 16

逆时针旋转90度后的图应该是：

            4 8 12 16 
            3 7 11 15 
            2 6 10 14 
            1 5 9 13
我们要如何原地进行操作以达到上面的效果呢？可以分两步 第一步交换主对角线两侧的对称元素，
第二步交换第i行和第n-1-i行，即得到结果。 看图示：

原图：           第一步操作后：   第二步操作后：
1 2 3 4              1 5 9 13         4 8 12 16
5 6 7 8              2 6 10 14       3 7 11 15
9 10 11 12        3 7 11 15       2 6 10 14

13 14 15 16      4 8 12 16       1 5 9 13

#include <iostream>
using namespace std;

void swap(int &x,int &y) {
	int k = x;
	x = y;
	y = k;
}
void Transpote(int array[][4],int n) {
	for(int i=0;i<n;i++)
		for(int j=i+1;j<n;j++)
			swap(array[i][j],array[j][i]);
	for(int i=0;i<n/2;i++)
		for(int j=0;j<n;j++)
			swap(array[i][j],array[n-i-1][j]);
}
int main() {
	int array[4][4] = {
		{1,2,3,4},
		{5,6,7,8},
		{9,10,11,12},
		{13,14,15,16}
	};
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)
			cout<<array[i][j]<< " ";
		cout<< endl;
	}
	cout<< endl;
	Transpote(array,4);
	for(int i=0;i<4;i++){
		for(int j=0;j<4;j++)
			cout<<array[i][j]<< " ";
		cout<< endl;
	}
	return 0;
}

2.将矩阵右旋转90度

有两个思路：
1 原矩阵计算出各个数值在新矩阵中的位置，然后一步到位转换成新的旋转矩阵
2 原矩阵到转置矩阵是很容易计算的，那么从转置矩阵到选择矩阵就只需要reverse每行的元素就可。

class Solution {
public:
    void rotate(vector<vector<int> > &matrix) {
        int n = matrix.size();
		for(int i=0; i< n/2;i++)
			for(int j=i;j < n-1-i; j++){
				int t = 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] = t;
				
			} 
    }
};

class Solution {
public:
   void rotate(vector<vector<int> > &matrix) {
		for(int i=0,n=matrix.size();i<n;++i){
			for(int j=i+1;j<n;++j)
				swap(matrix[i][j],matrix[j][i]);
			reverse(matrix[i].begin(),matrix[i].end());        
		}
	}
};

（2014.12.5更）