LeetCode 48. Rotate Image [Medium] [C++] 解題筆記

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

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.

EX:

        Given input matrix = 

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

    rotate the input matrix in-place such that it becomes:
    [
      [7,4,1],
      [8,5,2],
      [9,6,3]
    ]

想法:

    這題實作不難，只要知道方法基本都寫的出來。題目要求我們不使用額外空間完成 rotate，因此可以先求 array

的轉置之後在將對稱的行兩兩互換即可。

完整程式碼:

class Solution {
public:
    void swap(int& a, int& b) {
        auto temp = a;
        a = b;
        b = temp;
    }
    void transpose(vector<vector<int>>& matrix) {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = i + 1; j < matrix[i].size(); j++) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
    void reverse(vector<vector<int>>& matrix) {
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[i].size() / 2; j++) {
                swap(matrix[i][j], matrix[i][matrix[i].size() - 1 - j]);
            }
        }
    }
    void rotate(vector<vector<int>>& matrix) {
        transpose(matrix);
        reverse(matrix);
        return;
    }
};