runtime 0 ms, beats 100% of cpp submissions
O(n^2) solution with explanation

tags: math

Rotate Image

📖 description

給定一個 2 維陣列，將陣列旋轉 90 度，要求空間複雜度為 O(1) ，也就是必須 in place 的完成。

ex.
    Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]

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

🧠 solution

找到規律並模擬旋轉的操作，以底下的範例做解釋

在這題中，我們必須把 1 的位置給 13 ，假設 1 位在 i,j ，則藉由推倒，13 應該位在 n-j-1,i ，以此類推把四個角都推出來。

要注意的點是 i 只需要換到 (n+1)/2 ，因為當第一列換完後，會再從第二列開始換，此時第一行沒換ˋ到的部分就會被換到，而 j 只需要換到 n/2 ，因為只需要換到陣列的一半，後面就會被替換完成。

⏳ time complexity

總時間複雜度 **

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void rotate(vector<vector<int>>& m) {
        int n = m.size();
        int tmp = 0;
        for(int i=0;i<(n+1)/2;i++){
            for(int j=0;j<n/2;j++){

                // 推倒互換公式
                tmp = m[i][j];
                m[i][j] = m[n-j-1][i];
                m[n-j-1][i] = m[n-i-1][n-j-1];
                m[n-i-1][n-j-1] = m[j][n-i-1];
                m[j][n-i-1] = tmp;
            }
        }
    }
};