记一道有意思的算法题Rotate Image（旋转图像）
题出自https://leetcode.com/problems/rotate-image/ 内容为：
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up: Could you do this in-place?
简单的说就是给出一个n*n的二维数组，然后把这个数组进行90度顺时针旋转，而且不能使用额外的存储空间。
最初拿到这道题想到的就是找出每个坐标的旋转规律。假设我们是2*2的矩阵：
a b
c d进行旋转后，那么就变成了：
c a
d b所以就转换成对4个数字进行轮换，而不使用额外空间的问题。最常用的交换数值而不使用额外空间的算法就是异或，比如要交换a,b的值，那么可以写为：
a=a^b;
b=a^b;
a=a^b;现在是对4个数字进行轮换,轮换后的结果为a=c,b=a,c=d,d=b；
所以改写成异或的算法，那么就是：
a = a ^ b ^ c ^ d;
b = a ^ b ^ c ^ d;
d = a ^ b ^ c ^ d;
c = a ^ b ^ c ^ d;
a = a ^ b ^ c ^ d;接下来就是找出二维数组中角标与a,b,c,d的关系，这个其实不难。另外，我们在进行旋转处理时，我们只需要处理1/4的区域即可，因为处理一次就是调整了4个数，所以我们只处理二维数组中左上角的数值。
下面就是具体的代码：
public void Rotate(int[,] matrix)
{
int n = matrix.GetLength (0);
for (var i = 0; i < (n + 1)/2; i++)
{
for (var j = 0; j < n/2; j++)
{
//var a = matrix[i, j];
//var b = matrix[j, n - i - 1];
//var d = matrix[n - i - 1, n - j - 1];
//var c = matrix[n - j - 1, i];
matrix[i, j] = matrix[i, j] ^ matrix[j, n - i - 1] ^ matrix[n - i - 1, n - j - 1] ^ matrix[n - j - 1, i];
matrix[j, n - i - 1] = matrix[i, j] ^ matrix[j, n - i - 1] ^ matrix[n - i - 1, n - j - 1] ^ matrix[n - j - 1, i];
matrix[n - i - 1, n - j - 1] = matrix[i, j] ^ matrix[j, n - i - 1] ^ matrix[n - i - 1, n - j - 1] ^ matrix[n - j - 1, i];
matrix[n - j - 1, i] = matrix[i, j] ^ matrix[j, n - i - 1] ^ matrix[n - i - 1, n - j - 1] ^ matrix[n - j - 1, i];
matrix[i, j] = matrix[i, j] ^ matrix[j, n - i - 1] ^ matrix[n - i - 1, n - j - 1] ^ matrix[n - j - 1, i];
}
}
}使用异或并不是很直观，另外一个比较直观的交换两个数据的方法是加减法：
a=a+b;
b=a-b;
a=a-b;我们使用异或而不使用更直观的加减法是因为a+b的时候可能溢出，那么接下来的结果就不对了，所以不能用加减法而应该用异或。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2015-04-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
