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，時(shí)間復(fù)雜度o(n)：

順時(shí)針旋轉(zhuǎn)的規(guī)律很好找到，為了完全在矩陣內(nèi)部操作，普通的辦法就是每遍歷到一個(gè)位置，則將與這個(gè)位置相關(guān)的一周（旋轉(zhuǎn)一周涉及到的4個(gè)位置）都進(jìn)行替換操作。

代碼：

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，時(shí)間復(fù)雜度o(n):

拿出一張正方型紙，將紙順時(shí)針旋轉(zhuǎn)90度，相當(dāng)于先將紙向后反轉(zhuǎn)180度，再以左上-右下對(duì)角線為軸，旋轉(zhuǎn)180度。

所以，本題類似思路，先將矩陣按行反轉(zhuǎn)，在按左上-右下對(duì)角線為軸，做兩兩映射交換。

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 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/huxiao-tee/p/4338766.html

總結(jié)

以上是生活随笔為你收集整理的【Leetcode】【Medium】Rotate Image的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。