LeetCode面試題 01.07. 旋轉矩陣 多種解法O(1) C++描述

LeetCode面試題 01.07. 旋轉矩陣

大家好，我叫亓官劼（qí guān jié ），三本計算機在讀，目前在積極準備21計算機考研中，同時也在學習後端開發，準備工作。不敢孤注一擲，因為要留條後路；不求兩全其美在，因為那需要運氣+機遇；隻求學有所得，慢慢成長。CSDN中記錄學習的點滴曆程，時光荏苒，未來可期，加油~

每日一題 2020.04.07

難度 中等

題目

給你一幅由 N × N 矩陣表示的圖像，其中每個像素的大小為 4 位元組。請你設計一種算法，将圖像旋轉 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]

]

題解一：使用輔助數組

  旋轉矩陣應該是一個我們經常能看到的題目了，如果僅僅旋轉矩陣，我們并不困難，這裡使用一個輔助數組就可以進行輕松的實作，對于原數組​

​matrix[i][j]​

​​,我們複制一個新的數組​

​copy[i][j]​

​​，則我們旋轉後​

​copy[j][n - i - 1] = matrix[i][j];​

​，下面貼上完整的代碼：

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        auto copy = matrix;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                copy[j][n - i - 1] = matrix[i][j];
            }
        }
        matrix = copy;
    }
};      

執行情況為;

解法二：不使用額外存儲空間

  在解法一中我們使用了額外的數組進行了一次複制，有的小夥伴發現題目中有個進階的要求，就是不使用額外的空間來進行一個旋轉，這時候我們上面的方法就不好用了，因為我們解法一種需要旋轉時的中間狀态，是以必須要一個數組進行複制狀态。那我們該如何不使用額外空間來進行旋轉呢？

  這裡我們可以使用兩次翻轉來完成旋轉90度的操作，大家想想看，對于一個N*N的矩形，我們先上下旋轉一次，在沿着對角線旋轉一次(​​

​↘這個對角線哦!​

​)，是不是正好是旋轉了90！這個方法還更好寫代碼！下面就來看看代碼吧：

class Solution {
public:
    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 - i - 1][j]);
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};      

執行情況為：