LeetCode:旋转图像
题目描述
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
作者:力扣 (LeetCode)
链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目解析
例,输入输出如下图:
这个题目与其说是一道算法题,不如说是一道找规律得题目,我们怎样才能实现图像得90度旋转呢?通过对比输入输出图中数字得位置可以发现:我们可以将第一列得4个数通过顺时针旋转到第一行上,第一行顺时针旋转到最后一列上,一次类推;内圈的数字也要如此旋转,就可以完成题目要求,如下图:
有了思路之后,我们怎么通过算法实现呢?那就是找规律了。
首先,我们以数字5为例,看一下它以及和他有关的数字的变化路径:5->11 11->16 16->15 15->5;
其次,我们继续找规律,我们将上述数字集合线标来一遍:
5(0,0)->11(0,3)
11(0,3)->16(3,3)
16(3,3)->15(3,0)
15(3,0)->5(0,0)
从下标中我们能够发现有重复的下标相互转换数字,那么他们其中有什么内在的连续呢?我们现在找规律已经使用了数字转换流程,数字的下标,仔细想一下我们是不是还有一个关键的变量没有用到,那就是n*n;
最后,我们加上二维数组的行列长度再来一遍:
5([i]:0,[j]:0)->11([i]:0,[n-i或者j-1]:3)
11()
写到第二条的时候我发现写不下去了,这里的下标有大量的0和3,没有办法分辨是i还是j,写出来的规律也不能通用,因此我决定用数字1及其相关的数字类找规律(i=0,j=1)
首先,
1->10
10->12
12->13
13->1
其次,
1(0,1)->10(1,3)
10(1,3)->12(3,2)
12(3,2)->13(2,0)
13(2,0)->(0,1)
最后,
1([i]:0,[j]:1)->10([j]:1,[n-i-1]:3)
10([j]:1,[n-i-1]:3)->12([n-i-1]:3,[n-j-1]:2)
12([n-i-1]:3,[n-j-1]:2)->13([n-j-1]:2,[i]:0)
13([n-j-1]:2,[i]:0)->1([i]:0,[j]:1)
我们找到一下通用变量,有兴趣的可以套一下数字9及其相关数字的规律:
令:int m=n-i-1,c=n-j-1。
如下图示:
题目解答
算法1,时间复杂度为 o(n²),直接上代码如下:
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int row=matrix.size();
int colunm=matrix[0].size();
int length=row/2;
for(int i=0;i<length;i++)
{
for(int j=i;j<colunm-i-1;j++)
{
int m=row-i-1;
int n=row-j-1;
int temp=matrix[i][j];
matrix[i][j]=matrix[n][i];
matrix[n][i]=matrix[m][n];
matrix[m][n]=matrix[j][m];
matrix[j][m]=temp;
}
}
}
};
解题思路:解题思路再题目分析中已经详细阐明,此次不再累述。
最新文章
- Newtonsoft.Json设置类的属性不序列化
- GitHub实战系列~2.把本地项目提交到github中 2015-12-10
- error=Error Domain=NSURLErrorDomain Code=-1003
- js获取鼠标位置的各种方法
- 第K 小数
- 第一章 ------ AutoYout介绍
- node,不懂不懂
- 经验总结17--submitbutton,ajax提交
- 设置韩澳大利亚sinox弄winxp清除字体和界面美观
- WebService小记
- UNIX环境高级编程——可靠信号与不可靠信号
- 提升现代web app中页面性能
- JavaScript数据类型检测 数组(Array)检测方式
- 005_python对整数的拼接
- 手机端table表格bug
- linux 服务器脚本采集数据中文无法执行错误
- 近5年常考Java面试题及答案整理(一)
- [JSON].toXMLString()
- vue项目全局使用axios
- bzoj1494【Noi2007】生成树计数
热门文章
- Spring---IoC(控制反转)原理学习笔记【全】
- Oracle日志 归档模式管理
- Linux下的 sniff-andthen-spoof程序编写
- spark structured-streaming 最全的使用总结
- 攻防世界 WEB 高手进阶区 XCTF Web_php_unserialize Writeup
- mysql登录遇到ERROR 1045 (28000): Access denied for user &#39;root&#39;@&#39;localhost&#39; (using password: NO)
- Uncaught (in promise) Error: Request failed with status code 500解决方案
- Java 关键字之 final
- win8中让cmd.exe始终以管理员身份运行
- 单元测试NUnit,mock组件NSubstitute,信号量SemaphoreSlim,异步lock等例子