记一道有意思的算法题Rotate Image(旋转图像)-阿里云开发者社区

开发者社区> 人工智能> 正文

记一道有意思的算法题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的时候可能溢出,那么接下来的结果就不对了,所以不能用加减法而应该用异或。

本文转自深蓝居博客园博客,原文链接:http://www.cnblogs.com/studyzy/p/4406436.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
人工智能
使用钉钉扫一扫加入圈子
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

其他文章