【Leetcode】【Medium】Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

解题思路1，时间复杂度o(n)：

顺时针旋转的规律很好找到，为了完全在矩阵内部操作，普通的办法就是每遍历到一个位置，则将与这个位置相关的一周（旋转一周涉及到的4个位置）都进行替换操作。

代码：

1 class Solution { 2 public: 3 void rotate(vector<vector<int>>& matrix) { 4 int n = matrix.size() - 1; 5 for (int i = 0; i <= n / 2; ++i) { 6 for (int j = i; j < n - i; ++j) { 7 int reserve = matrix[i][j]; 8 int p = 4; 9 while (p--) { 10 if (p == 0) 11 matrix[i][j] = reserve; 12 else 13 matrix[i][j] = matrix[n-j][i]; 14 int tmp = i; 15 i = n - j; 16 j = tmp; 17 } 18 } 19 } 20 return; 21 } 22 };

 

解题思路2，时间复杂度o(n):

拿出一张正方型纸，将纸顺时针旋转90度，相当于先将纸向后反转180度，再以左上-右下对角线为轴，旋转180度。

所以，本题类似思路，先将矩阵按行反转，在按左上-右下对角线为轴，做两两映射交换。

1 class Solution { 2 public: 3 void rotate(vector<vector<int>>& matrix) { 4 reverse(matrix.begin(), matrix.end()); 5 for (int i = 0; i < matrix.size() - 1; ++i) { 6 for (int j = i; j < matrix.size(); ++j) { 7 swap(matrix[i][j], matrix[j][i]); 8 } 9 } 10 return; 11 } 12 };

 

转载于:https://www.cnblogs.com/huxiao-tee/p/4338766.html

总结

以上是生活随笔为你收集整理的【Leetcode】【Medium】Rotate Image的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。