一天一道算法题（11）：旋转数组的思路与实现解析

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;in;i{temp[i]make([]int,n)copy(temp[i],matrix[i])}left:n-1//把第n列放在第n行fori:0;in;i{forj:0;jn;j{matrix[i][j]temp[left][i]left--}leftn-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】放在【13】的位置上观察上面两组数据我们发现按照顺序排列之后后一个坐标的第一个元素等于前一个坐标的第二个元素即【ij】要放在【j…】的位置上而且i… n-1 … n-1-i所以坐标【ij】要放在坐标【jn-1-i】的位置上得出这个结论剩下的就简单了我们先来思考怎么去循环循环多少层的问题我们先来看n*n的矩阵我们发现34阶矩阵都是2圈再推广一下1,2阶矩阵都是一圈所以我们得出循环的圈数为floors : n/2 n%2那对于每一圈的元素每一次可以交换四个元素比如从左上角那个元素开始第二次要交换的元素就是从同一行的第二个元素开始循环我们拿4阶矩阵举例紧接着又会交换第3个元素然后结束第二圈只从第一个元素4交换完就结束了所以我们可以发现每一圈循环的最后一个元素的列的关系必须小于 n-1-当前的圈数到此我们就把所有的逻辑给盘清楚了接下来开始写代码funcrotate(matrix[][]int){n:len(matrix)//计算圈数floors:n/2n%2forf:0;ffloors;f{i,j:f,f//初始化第一个要交换的元素即每一圈左上角的元素//循环结束的条件是 当前的列小于n-1-当前的圈数forjn-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}}}-两次翻转先关于水平对轴上下翻转然后再关于主对角线对称反转即左上到右下的那条对角线这样的方式我就不写代码了欢迎大家自行思考结语这道题的难点在于合理的设计交换的逻辑和循环的条件没有思路的时候停下来多去列举被交换数字的下标能很快发现下标变换规律从而设计出正确的交换算法如果喜欢该算法系列欢迎大家关注订阅我会经常更新力扣算法题解