Rotate Image

主对角线上的元素是(i,i)，(0, 0), (1, 1), (2, 2).....

主对角线右边的元素 i from 0 to n - 1, j from i+1, to n-1 , 对应主对角线左边的元素matrix[i][j] map matrix[j][i]

副对角线上的元素是 (i, n-1-i), (0,3), (1,2), (2,1), (3,0) ...n=4.

副对角线左边的元素i from 0 to n - 1 j from 0 to n-1-i对应副对角线右边的元素matrix[i][j] map matrix[n-1-j][n-1-i]

// Rotate Image
// 思路 1，时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();

        for (int i = 0; i < n; ++i)  // 沿着副对角线反转
            // also OK
            //for (int j = 0; j < n - i; ++j)
            for (int j = 0; j < n - i - 1; ++j)
                swap(matrix[i][j], matrix[n - 1 - j][n - 1 - i]);

        for (int i = 0; i < n / 2; ++i) // 沿着水平中线反转
            for (int j = 0; j < n; ++j)
                swap(matrix[i][j], matrix[n - 1 - i][j]);
    }
};

// Rotate Image
// 思路 1，时间复杂度O(n^2)，空间复杂度O(1)
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const 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 + 1; j < n; ++j)
                swap( matrix[i][j], matrix[j][i]);
    }
};