leetcode----面試題 01.07. 旋轉矩陣

題目連結--------------->leetcode----面試題 01.07. 旋轉矩陣

這個題隻要我們自己手動模拟一邊旋轉過程，很容易就找出規律來。

方法一：對于一個 n u m [ i ] [ j ] num[i][j] num[i][j]來說它旋轉後的位置為 n u m [ j ] [ n − 1 − i ] num[j][n-1-i] num[j][n−1−i]，我們使用一個數組來儲存原數組的值，然後雙重循環對原數組指派即可。

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size(),m = matrix[0].size();
    vector<vector<int>> num(matrix.begin(),matrix.end());
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            matrix[j][n - 1 - i] = num[i][j];
        }
    }
}
           

方法二：上述方法要使用額外數組，是因為在轉換的過程中會把目标位置的數給覆寫掉，是以要使用一個數組來儲存它們的值。其實完全沒必要多用一個數組，我們可以看下述例子

假設我們即将要旋轉的數字為 n u m [ i ] [ j ] num[i][j] num[i][j]

1. n u m [ i ] [ j ] num[i][j] num[i][j]被旋轉到的位置為 n u m [ j ] [ n − 1 − i ] num[j][n-1-i] num[j][n−1−i]

2. n u m [ j ] [ n − 1 − i ] num[j][n-1-i] num[j][n−1−i]被旋轉到的位置為 n u m [ n − 1 − i ] [ n − 1 − j ] num[n-1-i][n-1-j] num[n−1−i][n−1−j]

3. n u m [ n − 1 − i ] [ n − 1 − j ] num[n-1-i][n-1-j] num[n−1−i][n−1−j]被旋轉到的位置為 n u m [ n − 1 − j ] [ i ] num[n-1-j][i] num[n−1−j][i]

4. n u m [ n − 1 − j ] [ i ] num[n-1-j][i] num[n−1−j][i]被旋轉到的位置為 n u m [ i ] [ j ] num[i][j] num[i][j]

我們可以發現這是一個閉環，是以在對一個數字旋轉時，為了避免目标位置的數字被覆寫我們可以一次将這四個數全部都旋轉。此時我們并不需要一個二維數組，而隻需要一個變量

由于我們一次需要操作便可旋轉4個數，是以我們要确定枚舉的邊界。我們對于一個需要旋轉的二維數組通過上述方法來模拟一遍，很容易就找到邊界。

第一層的邊界為 n / 2 n/2 n/2，第二層的邊界為 n − 1 − i n-1-i n−1−i。

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for(int i = 0;i < n/2;i++)
    {
        for(int j = i;j < n - 1 - i;j++)
        {
            int tmp = matrix[j][n - 1 - i];
            matrix[j][n - 1 - i] = matrix[i][j];
            matrix[i][j] = matrix[n - 1 - j][i];
            matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];
            matrix[n - 1 - i][n - 1 - j] = tmp;
        }
    }
}
           

看了題解後發現還有一種更好的做法

方法三：我們對二維數組先水準翻轉，然後再按主對角線翻轉。

水準翻轉： n u m [ n − 1 − i ] [ j ] = n u m [ i ] [ j ] num[n-1-i][j]=num[i][j] num[n−1−i][j]=num[i][j]，主對角線反轉： n u m [ j ] [ i ] = n u m [ i ] [ j ] num[j][i]=num[i][j] num[j][i]=num[i][j]。

将上面兩個式子合并可得到 n u m [ j ] [ n − 1 − i ] = n u m [ i ] [ j ] num[j][n-1-i]=num[i][j] num[j][n−1−i]=num[i][j]，可以看出這正是我們方法一中的式子。

void rotate(vector<vector<int>>& matrix) {
    int n = matrix.size();
    for(int i = 0;i < n/2;i++)
    {
        for(int j = 0;j < n;j++)
        {
            swap(matrix[i][j],matrix[n - 1 - i][j]);
        }
    }
    for(int i = 0;i < n;i++)
    {
        for(int j = i;j < n;j++)
            swap(matrix[i][j],matrix[j][i]);
    }
}