锐客网

  1. 首页 > it技术 > >

LeetCode:旋转图像

题目描述 给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnhhkv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
题目解析 例，输入输出如下图：
LeetCode:旋转图像
文章图片
这个题目与其说是一道算法题，不如说是一道找规律得题目，我们怎样才能实现图像得90度旋转呢？通过对比输入输出图中数字得位置可以发现：我们可以将第一列得4个数通过顺时针旋转到第一行上，第一行顺时针旋转到最后一列上，一次类推；内圈的数字也要如此旋转，就可以完成题目要求，如下图：
LeetCode:旋转图像
文章图片
有了思路之后，我们怎么通过算法实现呢？那就是找规律了。
首先，我们以数字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)
  • 【LeetCode:旋转图像】13([n-j-1]:2,[i]:0)->1([i]:0,[j]:1)
我们找到一下通用变量，有兴趣的可以套一下数字9及其相关数字的规律：
令：int m=n-i-1,c=n-j-1。
如下图示：
LeetCode:旋转图像
文章图片
题目解答 算法1，时间复杂度为 o(n2),直接上代码如下：
class Solution { public: void rotate(vector>& matrix) { int row=matrix.size(); int colunm=matrix[0].size(); int length=row/2; for(int i=0; i
解题思路：解题思路再题目分析中已经详细阐明，此次不再累述。

    推荐阅读


    上一篇：8.7|8.7 进程间的通讯（管道、消息队列、共享内存、信号量、信号、Socket）

    下一篇：SpringBoot|SpringBoot 整合 MyBatis，实现 CRUD 示例