LeetCode 48. 旋转图像
2020-04-07 16:03:27来源:博客园 阅读 ()
LeetCode 48. 旋转图像
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 48. 旋转图像
题目
给定一个 n?×?n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明:
你必须在__原地__旋转图像,这意味着你需要直接修改输入的二维矩阵。__请不要__使用另一个矩阵来旋转图像。
示例 1:
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
示例 2:
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],
原地旋转输入矩阵,使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/rotate-image
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
本题实际不难,仔细分析旋转过程中的坐标转换就可以了,可以拿个例子画一画;
思路1-原地旋转,找坐标的对应关系规律
以:[
[1,2,3],
[4,5,6],
[7,8,9]
],
为例,其坐标为:
[0,0],[0,1],[0,2],
[1,0],[1,1],[1,2],
[2,0],[2,1],[2,2],
分析第一排[0,0],[0,1],[0,2],旋转后的每个坐标的变化:
对于[0,0]:
[0,0]->[2,0]->[2,2]->[0,2]->[0,0];
对于[0,1]:
[0,1]->[1,0]->[2,1]->[1,2]->[0,1];
对于[0,2]:
[0,2]->[0,0]->[2,0]->[2,2]->[0,2];
对这三个坐标的每一步分析后就会发现一个规律,
对于坐标[i,j]:
-
[i,j]->[N - j - 1][i]->[N - i - 1][N - j - 1]->[j][N - i - 1]-[i,j];
-
算法的核心便基于此,另外需要注意的是每一次外层旋转完成后,i的起始坐标就要+1,j的起始坐标等于i,并且j的范围为[i,N-1-i];
算法复杂度:
- 时间复杂度:O(n2)
- 空间复杂度:O(1)
算法源码示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年2月2日 下午9:17:23
* @Description: 48. 旋转图像
*
*/
public class LeetCode_0048 {
}
class Solution_0048 {
/**
* @author: ZhouJie
* @date: 2020年2月4日 下午10:41:04
* @param: @param matrix
* @return: void
* @Description: 1-
*
*/
public void rotate(int[][] matrix) {
if (matrix == null) {
return;
}
int len = matrix.length, temp;
for (int i = 0; i < len / 2; ++i) {
for (int j = i; j < len - i - 1; j++) {
temp = matrix[i][j];
matrix[i][j] = matrix[len - 1 - j][i];
matrix[len - 1 - j][i] = matrix[len - 1 - i][len - 1 - j];
matrix[len - 1 - i][len - 1 - j] = matrix[j][len - 1 - i];
matrix[j][len - 1 - i] = temp;
}
}
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12653544.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- LeetCode 287. 寻找重复数 2020-05-31
- LeetCode 5. 最长回文子串 2020-05-22
- LeetCode 21. 合并两个有序链表 2020-05-22
- LeetCode 面试题55 - I. 二叉树的深度 2020-05-22
- LeetCode 104. 二叉树的最大深度 2020-05-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash