[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;
}
}
}
补充：综合编程 , 其他综合 ,
