[google面试CTCI] 1-6.图像旋转问题


		【字符串与数组】
 
Q：Given an image represented by an NxN matrix, where each pixel in the image is 4
bytes, write a method to rotate the image by 90 degrees Can you do this in place?
 
题目：假定一幅图像能用NxN的矩阵表示，每个像素是四字节。写一个算法将图像旋转90度，你能否在原地进行操作（也即不分配额外的存储空间）？
 
解答：
 
我们不知道具体该如何操作，但有一点可以肯定的是，需要通过交换一些元素的位置来达到旋转的目的。具体怎么交换，我们可以通过画一个小矩阵来寻找方法。
 
假设我们将图像逆时针旋转90度  ，对于一个4x4的图像，假设其各个值如下：
 
1      2    3    4
 
5      6    7    8
 
9     10  11  12
 
13  14  15   16
 
目标状态如下：
 
4    8    12     16   
 
3    7    11     15
 
2    6    10     14
 
1    5    9       13
 
是不是还没看出规律来？要将图像旋转90度,我们有一个很直观的观察结果是：对角线两边对称元素有一个互换的过程。要不我们先交换对角线两边的元素看看：
 
1    5    9     13
 
2    6    10   14
 
3    7    11   15
 
4    8    12    16
 
现在看出规律来了没？将上图与最终的旋转结果比较，发现它跟最终的旋转结果是按行首尾对称的，将上图首尾对称的列交换，即可得到最终结果。
 
即先交换对角线元素，再交换首尾行(第一行与最后一行交换，第二行与倒数第二行交换等…),至此，可以编码如下:
 
#define N 4
void rotate(int matrix[][N]){
int i,j;
int iTmp;
for(i=0;i<N;++i){
for(j=i+1;j<N;++j){
iTmp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=iTmp;
}
}
for(i=0;i<N/2;++i){
for(j=0;j<N;++j){
iTmp=matrix[i][j];
matrix[i][j]=matrix[n-i-1][j];
matrix[n-i-1][j]=iTmp;
}
}
}

补充：综合编程 , 其他综合 ,