給定一個 n?×?n 的二維矩陣表示一個圖像。

將圖像順時針旋轉 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] ]

宏觀調度

一層一層旋轉，最外面一層按照某種對應規則逐步旋轉，然后由外而內一層一層推進，直到完成。

對應規則也很簡單，對于當前層級，四個四個換，首先把四個角上的元素旋轉，然后往前走一步再旋轉。

Python

class Solution:def rotate(self, matrix: List[List[int]]) -> None:"""Do not return anything, modify matrix in-place instead."""# 當前旋轉邊的左上角和右下角leftTopRow, leftTopCol, rightDownRow, rightDownCol = 0, 0, len(matrix) - 1, len(matrix[-1]) - 1while leftTopRow <= rightDownRow and leftTopCol < rightDownRow:# 按照對應規則逐步旋轉for i in range(rightDownCol - leftTopCol):matrix[leftTopRow][leftTopCol + i], matrix[leftTopRow + i][rightDownCol], \matrix[rightDownRow][rightDownCol - i], matrix[rightDownRow - i][leftTopCol], = \matrix[rightDownRow - i][leftTopCol], matrix[leftTopRow][leftTopCol + i], \matrix[leftTopRow + i][rightDownCol], matrix[rightDownRow][rightDownCol - i]# 完成旋轉后更新層級leftTopRow += 1leftTopCol += 1rightDownRow -= 1rightDownCol -= 1

復雜度分析

• 時間復雜度：O(N²)，外層while循環由于左上角和右下角同時走，N/2，里面for循環長度為矩陣一行的長度，N，所以O(N/2*N)=O(N²/2)=O(N²)
• 空間復雜度：O(1)
  

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的《每日一题》48. Rotate Image 旋转图像的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。