LeetCode中二維數組如何實現旋轉矩陣

LeetCode中二維數組如何實現旋轉矩陣

在LeetCode等編程競賽平臺中，二維數組的旋轉矩陣是一個常見的算法問題。這類問題通常要求我們將一個二維數組（矩陣）按照順時針或逆時針方向旋轉90度、180度或270度。本文將詳細介紹如何實現二維數組的旋轉矩陣，并提供一個具體的代碼示例。

1. 問題描述

給定一個 n x n 的二維矩陣 matrix，要求將其順時針旋轉90度。旋轉后的矩陣應該直接修改原矩陣，而不是返回一個新的矩陣。

例如，給定矩陣：

1 2 3
4 5 6
7 8 9

旋轉90度后應該變為：

7 4 1
8 5 2
9 6 3

2. 解決思路

要實現矩陣的旋轉，我們可以采用以下步驟：

1. 轉置矩陣：將矩陣的行和列互換。例如，矩陣中的元素 matrix[i][j] 會變成 matrix[j][i]。
2. 反轉每一行：將轉置后的矩陣的每一行進行反轉。

通過這兩個步驟，我們可以實現矩陣的順時針旋轉90度。

2.1 轉置矩陣

轉置矩陣的操作是將矩陣的行和列互換。對于一個 n x n 的矩陣，轉置操作可以通過以下代碼實現：

for i in range(n):
    for j in range(i, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

2.2 反轉每一行

轉置后的矩陣的每一行需要進行反轉。反轉操作可以通過以下代碼實現：

for i in range(n):
    matrix[i].reverse()

3. 代碼實現

結合上述兩個步驟，我們可以實現矩陣的順時針旋轉90度。以下是完整的Python代碼：

def rotate(matrix):
    n = len(matrix)
    
    # Step 1: Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()

3.1 示例

讓我們通過一個示例來驗證這個算法。假設我們有以下矩陣：

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

調用 rotate(matrix) 后，矩陣將變為：

[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]

4. 復雜度分析

• 時間復雜度：轉置矩陣的時間復雜度為 O(n^2)，反轉每一行的時間復雜度為 O(n)，因此總的時間復雜度為 O(n^2)。
• 空間復雜度：由于我們直接在原矩陣上進行操作，沒有使用額外的空間，因此空間復雜度為 O(1)。

5. 其他旋轉角度

除了順時針旋轉90度，我們還可以通過類似的方法實現其他角度的旋轉：

• 逆時針旋轉90度：可以先反轉每一行，然后再轉置矩陣。
• 旋轉180度：可以先將矩陣上下翻轉，然后再左右翻轉。
• 旋轉270度：可以先轉置矩陣，然后再反轉每一列。

6. 總結

通過轉置矩陣和反轉每一行的操作，我們可以高效地實現二維數組的旋轉矩陣。這種方法不僅簡單易懂，而且具有較低的時間和空間復雜度。在實際編程競賽中，掌握這種技巧可以幫助我們快速解決類似的問題。

希望本文對你理解如何在LeetCode中實現二維數組的旋轉矩陣有所幫助！