题目

链接

分析

来观察下正方形矩阵旋转90度时究竟发生了什么。

观察图中颜色相同的四个位置，当旋转90度后，对应位置的元素发生了顺时针的交换。

而相隔的两个位置是中心对称的，基于此可以计算出发生交换的四个元素位置关系。
设四个位置中，位于左上角区域的位置坐标为 (i,j)，
则按顺时针顺序，四个位置分别为(i,j), (j, n-i-1), (n-i-1,n-j-1), (n-j-1,i)。
其中 n 为 matrix.size(), i, j 分别为matrix的行列下标，从 0 开始。

整个矩阵的旋转可以理解为起点都在左上角区域，然后依次顺时针移动

matrix.size() 为奇数时，位置的对应关系相同，但左上角区域并不是整个矩阵的四分之一，如下图示：

其实就是多了中间列的上半部分。

那么现在捋一下如何原地操作元素：
枚举左上区域的所有位置，然后通过上面总结的位置关系直接交换元素。
对于一个位置 (i,j)，需要交换三次：

1. $swap(matrix[i][j],matrix[j][n-i-1]);$
2. $swap(matrix[i][j],matrix[n-i-1][n-j-1]);$
3. $swap(matrix[i][j],matrix[n-j-1][i]);$

综上，整个过程的时间复杂度为O(n^2)；空间复杂度为(1)。

有小伙伴对坐标推导过程感兴趣，那我尝试讲一下：

这样就得到了其中一对位置的坐标对应关系，另一对和该对是根据对角线对称的，证明过程类似，不再赘述啦。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if(n == 0) { return; }
        int r = (n>>1)-1; //左上角区域的最大行下标，
        int c = (n-1)>>1; //左上角区域的最大列下标，行列下标从 0 开始。
        for(int i = r; i >= 0; --i) {
            for(int j = c; j >= 0; --j) {
                swap(matrix[i][j], matrix[j][n-i-1]);
                swap(matrix[i][j], matrix[n-i-1][n-j-1]);
                swap(matrix[i][j], matrix[n-j-1][i]);
            }
        }
    }
};

java实现

import java.util.Arrays;

public class Solution {

    // 4 个数轮换，大风车转呀转悠悠

    public void rotate(int[][] matrix) {
        int N = matrix.length;
        for (int i = 0; i < N / 2; i++) {
            for (int j = i; j < N - i - 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[N - j - 1][i];
                matrix[N - j - 1][i] = matrix[N - i - 1][N - j - 1];
                matrix[N - i - 1][N - j - 1] = matrix[j][N - i - 1];
                matrix[j][N - i - 1] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = {
                {5, 1, 9, 11},
                {2, 4, 8, 10},
                {13, 3, 6, 7},
                {15, 14, 12, 16}
        };

        Solution solution = new Solution();
        solution.rotate(matrix);

        for (int[] row : matrix) {
            System.out.println(Arrays.toString(row));
        }
    }
}

方法二：利用翻转代替旋转

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]);
            }
        }
    }
};

我们还可以另辟蹊径，用翻转操作代替旋转操作。我们还是以题目中的示例二

 5  1  9 11
 2  4  8 10
13  3  6  7
15 14 12 16

作为例子，先将其通过水平轴翻转得到：

 5  1  9 11                 15 14 12 16
 2  4  8 10                 13  3  6  7
------------   =水平翻转=>   ------------
13  3  6  7                  2  4  8 10
15 14 12 16                  5  1  9 11

再根据主对角线 \ 翻转得到：

15 14 12 16                   15 13  2  5
13  3  6  7   =主对角线翻转=>   14  3  4  1
 2  4  8 10                   12  6  8  9
 5  1  9 11                   16  7 10 11

就得到了答案。这是为什么呢？对于水平轴翻转而言，我们只需要枚举矩阵上半部分的元素，和下半部分的元素进行交换

java实现

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        // 先以对角线（左上-右下）为轴进行翻转
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        // 再对每一行以中点进行翻转
        int mid = n >> 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < mid; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = tmp;
            }
        }
    }
}

j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - 1 - j];
matrix[i][n - 1 - j] = tmp;
}
}
}
}