48. 旋转图像
文章目录
- [48. 旋转图像](https://leetcode.cn/problems/rotate-image/)
- - **复制数组暴力(不超时，但是题目不允许这样)**
- - **原地旋转**
- - **两次翻转**
- 结语
- ==如果喜欢该算法系列，欢迎大家关注订阅，我会经常更新力扣算法题解！！！==
给定一个n×n的二维矩阵matrix表示一个图像。请你将图像顺时针旋转 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]]思路
-复制数组暴力(不超时，但是题目不允许这样)
funcrotate(matrix[][]int){n:=len(matrix)temp:=make([][]int,n)//复制数组fori:=0;i<n;i++{temp[i]=make([]int,n)copy(temp[i],matrix[i])}left:=n-1//把第n列放在第n行fori:=0;i<n;i++{forj:=0;j<n;j++{matrix[i][j]=temp[left][i]left--}left=n-1}}
-原地旋转
我觉得这道题目难点在于非常难思考到数字交换的算法，所以我直接多举例子，观察得出规律
我们看这四个位置的元素，【0,0】，【0,3】，【3,3】，【3,0】，分别对应的是5,11,16,15，现在，我们要把16放在5的位置，16放在15的位置，11放在16的位置，5放在11的位置，现在我们还不好确定这个规律，但是我们大致发现，一定是围绕着n-1这个数据来计算这其中的规律，我们再来看下一组数据，分别是【0,1】，【1,3】，【3,2】，【2,0】，我们知道，按照我们列举的这个顺序，前一个元素要放在后一个元素的位置上，即【0,1】放在【1，3】的位置上，观察上面两组数据，我们发现按照顺序排列之后，后一个坐标的第一个元素等于前一个坐标的第二个元素，即【i，j】要放在【j，…】的位置上，而且i+… = n-1 => … = n-1-i，所以，坐标【i，j】要放在坐标【j，n-1-i】的位置上，得出这个结论，剩下的就简单了，我们先来思考怎么去循环，循环多少层的问题，我们先来看n*n的矩阵，我们发现3，4阶矩阵都是2圈，再推广一下1,2阶矩阵都是一圈，所以我们得出循环的圈数为floors := n/2 + n%2，那对于每一圈的元素，每一次可以交换四个元素，比如从左上角那个元素开始，第二次要交换的元素就是从同一行的第二个元素开始循环，我们拿4阶矩阵举例，紧接着又会交换第3个元素，然后结束，第二圈只从第一个元素4交换完就结束了，所以我们可以发现，每一圈循环的最后一个元素的列的关系，必须小于 n-1-当前的圈数，到此，我们就把所有的逻辑给盘清楚了，接下来开始写代码
funcrotate(matrix[][]int){n:=len(matrix)//计算圈数floors:=n/2+n%2forf:=0;f<floors;f++{i,j:=f,f//初始化第一个要交换的元素，即每一圈左上角的元素//循环结束的条件是 当前的列小于n-1-当前的圈数forj<n-f-1{//golang里面可以直接交换，别的编程语言可以引入temp来记录第一个元素的值继续交换matrix[i][j],matrix[n-1-j][i],matrix[n-1-i][n-1-j],matrix[j][n-1-i]=matrix[n-1-j][i],matrix[n-1-i][n-1-j],matrix[j][n-1-i],matrix[i][j]//交换完4个元素之后j++，向右移动一个单位，继续交换新的四个元素j++}}}-两次翻转
- 先关于水平对轴上下翻转，然后再关于主对角线对称反转（即左上到右下的那条对角线），这样的方式我就不写代码了，欢迎大家自行思考
结语
这道题的难点在于合理的设计交换的逻辑和循环的条件，没有思路的时候停下来多去列举被交换数字的下标，能很快发现下标变换规律，从而设计出正确的交换算法