DAY 29 試題

問題描述

給定一個 n x 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]]

限制條件：

• n == matrix.length == matrix[i].length
• 1 <= n <= 20
• -1000 <= matrix[i][j] <= 1000

解題思路

要將矩陣進行順時針旋轉 90 度，我們可以通過以下兩個步驟完成：

1. 矩陣轉置：

• 將矩陣的行列互換，也就是 matrix[i][j] 變成 matrix[j][i]。
• 這樣做會使矩陣中原本在行的數據轉移到列，進而使矩陣看起來像是順時針旋轉。

2. 反轉每一行：

• 轉置後的矩陣仍然不完全是順時針旋轉 90 度的結果，因此我們需要反轉每一行，將每行的元素進行左右對調。
  這兩個步驟就能讓我們在原地將矩陣旋轉 90 度。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        
        // 步驟1：矩陣轉置
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
        
        // 步驟2：反轉每一行
        for (int i = 0; i < n; ++i) {
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

解法重點與分析

1. 轉置矩陣：

• 轉置操作是將矩陣的行和列互換。在轉置的過程中，對於每個 matrix[i][j]，我們將其與 matrix[j][i] 交換。這樣能將矩陣「斜對角」進行翻轉，行變成列。
• 這樣的結果是矩陣左上角和右下角的元素互換，而不會破壞其他元素的位置。

2. 反轉每一行：

• 完成轉置後，我們需要將每一行的數據進行左右反轉，這樣才能得到順時針旋轉 90 度的結果。
• 這一步操作是為了讓矩陣的列順序變成正確的順時針方向。

複雜度分析

1. 時間複雜度：

• 轉置矩陣的時間複雜度是 O(n^2)，因為我們需要遍歷矩陣的每一個元素並進行互換。
• 反轉每一行的時間複雜度是 O(n^2)，因為每一行需要進行反轉操作。
• 總時間複雜度是 O(n^2)。

2. 空間複雜度：

• 空間複雜度為 O(1)，因為我們是「原地」進行操作，沒有使用額外的存儲空間。

總結

這道題透過矩陣的轉置和反轉操作，可以在不分配額外空間的情況下完成矩陣順時針旋轉 90 度。這個解法不僅操作簡潔，而且符合題目要求的時間與空間限制。

以上是第二十九天的自學內容分享，謝謝大家。