48. Rotate Image

難度: Medium

類型: Array, Math, Matrix 

CPP程式下載: 48.cpp

前情題要:

n*n 的 2D 矩陣, 順時鐘方向轉九十度, 必須就地(in-place)完成, 也就是改在 input matrix 上的意思。

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

 

Example 1:

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

Example 2:

Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

 

Constraints:

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

思考方式:

1. 轉九十度, 多舉幾個例子找規律, (0,0) -> (0,2) -> (2,2) -> (2,0)。 (0,1) -> (1,3) -> (3,2) -> (2,0)

2. 每個數字, 轉四次90度就回到原位。所以要做三次旋轉, 然後第四個位置就是原位, 填上最後一個值。

3. 決定要做那些數字就好, 原則上用 1/4 的位置點去操作就可以, 剩下的點旋轉的時候就會被更新到, 不然就是最中間那個點不須旋轉。

4. 拿右上到左下的對角線, 在這對角線左上方的數字(不含對角線自己)才需要當作旋轉運算的起始點。拿左上到右下的對角線, 在這對角線右上方(含對角線自己)才需要當作旋轉運算的起始點。

5. 記得印出你操作點的(i,j)座標, 確保你的邊界以及運算符合自己的想法。最後 submit 前, 記得把 cout 拿乾淨, 以免影響 Runtime。

複雜度思考:

Time Complexity: Worst case: O( N*N/4 )

Space Complexity: O( x )

結果:

Runtime: 0 ms, Beats: 100%

Memory: 10.22 MB, Beats: 34.72%

Accepted

21 / 21 testcases passed

tendchen

submitted at Nov 11, 2025 11:49

Runtime

0ms

Beats100.00%

Analyze Complexity

Memory

10.22MB

Beats34.72%

Analyze Complexity

Code

C++

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int iSize_matrix = matrix.size();
        vector<int> row;
        int iSize_row;
        int iTemp;
        int i,j;
        //cout << "iSize_matrix =" << iSize_matrix << "\n";
        //row = matrix.at(0);
        //iSize_row = row.size();
        //cout << "iSize_row =" << iSize_row << "\n";
        //cout << "row = " << row.at(0) << " " << row.at(1) << "\n";
        for (i=0;i<((iSize_matrix+1)/2);i++)
        {
            for (j=i;j<(iSize_matrix-1-i);j++)
            {
                //cout << "i=" << i << ", j=" << j << "\n";
                //cout << "matrix[i][j]=" << (matrix.at(i)).at(j) << "\n";
                iTemp=matrix[j][iSize_matrix-1-i];
                matrix[j][iSize_matrix-1-i]=matrix[i][j];
                matrix[i][j]=iTemp;

                iTemp=matrix[iSize_matrix-1-i][iSize_matrix-1-j];
                matrix[iSize_matrix-1-i][iSize_matrix-1-j]=matrix[i][j];
                matrix[i][j]=iTemp;

                iTemp=matrix[iSize_matrix-1-j][i];
                matrix[iSize_matrix-1-j][i]=matrix[i][j];
                matrix[i][j]=iTemp;
            }
        }
    }
};