首先,我們來看兩張圖,不知道你有沒有發現這個圖和微軟的圖示好像啊~~~~
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5SO0MDM0gTY0ITZ1MTYwQ2NxYzX1QjMwcTMwMzLcBTMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL2M3Lc9CX6MHc0RHaiojIsJye.png)
問題描述
有一個 NxN 整數矩陣,請編寫一個算法,将矩陣順時針旋轉90度。
要求:時間複雜度O(N2),空間複雜度是O(N2)。
進階:時間複雜度是O(N^2),空間複雜度是O(1)
示例:
[ [
[ 5, 1, 9,11], 旋轉90度後 [15,13, 2, 5],
[ 2, 4, 8,10], ============> [14, 3, 4, 1],
[13, 3, 6, 7], [12, 6, 8, 9],
[15,14,12,16] [16, 7,10,11]
] ]
分析問題
對于矩陣中的第一行元素來說,在經過90度旋轉後,出現在了倒數第一列的位置上,如下圖所示。
并且,第一行的第 i 個元素在旋轉後恰好是倒數第一列的第 i 個元素。對于第二行的元素也是如此,在旋轉後變成倒數第二列的元素,并且第二行的第i個元素在旋轉後恰好是倒數第二列的第i個元素。是以,我們可以得出規律,對于矩陣中第 i 行的第 j 個元素,在旋轉後,它出現在倒數第 i 列的第 j 個位置,即對于矩陣中的 matrix[i] [j] 元素,在旋轉後,它的新位置為 matrix [j] [n-i-1]。
是以,我們申請一個大小為 n * n 的新矩陣,來臨時存儲旋轉後的結果。我們通過周遊matrix中的所有元素,根據上述規則将元素存放到新矩陣中的對應位置。在周遊完成後,再将新矩陣中複制到原矩陣即可。下面我們來看一下代碼實作。
class Solution(object):
def rotate(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: None Do not return anything, modify matrix in-place instead.
"""
#矩陣的大小
n = len(matrix)
#申請一個輔助矩陣
temp = [[0] * n for _ in range(n)]
#周遊矩陣中的所有元素,放到輔助矩陣的相應位置中
for i in range(n):
for j in range(n):
temp[j][n - i - 1] = matrix[i][j]
#将輔助矩陣複制給矩陣
matrix[:] = temp
該算法的時間複雜度是O(N2),空間複雜度O(N2)。
進階
那我們如何在不使用輔助空間的情況下,實作矩陣的原地旋轉呢?我們來看一下方法一中為什麼要引入輔助空間,對于matrix中的元素,我們使用公式temp[j] [n - i - 1] = matrix[i] [j]進行旋轉,如果不申請輔助矩陣,我們直接把元素 matrix[i] [j],放到矩陣 matrix[j] [n - i - 1]位置,原矩陣中的matrix[j] [n - i - 1]元素就被覆寫了,這顯然不是我們要的結果。
當知道了如何原地旋轉矩陣之後,這裡還有一點需要明确:我們應該選取哪些位置進行上述的原地交換操作呢?通過上面的分析可以知道,一次可以原地交換四個位置,是以:
- 當n為偶數時,我們需要選取 n^2 / 4 = (n/2) * (n/2)個元素進行原地交換操作,可以将該圖形分為四塊,可以保證不重複、不遺漏旋轉所有元素;
- 當n為奇數時,由于中心的位置經過旋轉後位置不變,我們需要選取 (n^2-1)/4=(n-1)/2 * (n+1) /2個元素進行原地交換操作,我們以5*5的矩陣為例,可以按照以下方式劃分,進而保證不重複、不遺漏的旋轉所有元素。
class Solution(object):
def rotate(self, matrix):
#矩陣的大小
n = len(matrix)
for i in range(n // 2):
for j in range((n + 1) // 2):
#進行一輪原地旋轉,旋轉4個元素
temp = matrix[i][j]
matrix[i][j] = matrix[n - j - 1][i]
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]
matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]
matrix[j][n - i - 1] = temp