# 48. Rotate Image (M)

You are given an `n x n` 2D `matrix` representing an image, rotate the image by **90** degrees (clockwise).

You have to rotate the image [**in-place**](https://en.wikipedia.org/wiki/In-place_algorithm), which means you have to modify the input 2D matrix directly. **DO NOT** allocate another 2D matrix and do the rotation.

 

**Example 1:**

![](https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg)

```
Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]
```

**Example 2:**

![](https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg)

```
Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
```

 

**Constraints:**

* `n == matrix.length == matrix[i].length`
* `1 <= n <= 20`
* `-1000 <= matrix[i][j] <= 1000`

### Solution:

题目很好理解，就是让你将一个二维矩阵顺时针旋转 90 度，**难点在于要「原地」修改**，函数签名如下：

```java
void rotate(int[][] matrix)
```

如何「原地」旋转二维矩阵？稍想一下，感觉操作起来非常复杂，可能要设置巧妙的算法机制来「一圈一圈」旋转矩阵：

[![](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/1.png)](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/1.png)

**但实际上，这道题不能走寻常路**，在讲巧妙解法之前，我们先看另一道谷歌曾经考过的算法题热热身：

给你一个包含若干单词和空格的字符串 `s`，请你写一个算法，**原地**反转所有单词的顺序。

比如说，给你输入这样一个字符串：

```shell
s = "hello world labuladong"
```

你的算法需要**原地**反转这个字符串中的单词顺序：

```shell
s = "labuladong world hello"
```

常规的方式是把 `s` 按空格 `split` 成若干单词，然后 `reverse` 这些单词的顺序，最后把这些单词 `join` 成句子。但这种方式使用了额外的空间，并不是「原地反转」单词。

**正确的做法是，先将整个字符串 `s` 反转**：

```shell
s = "gnodalubal dlrow olleh"
```

**然后将每个单词分别反转**：

```shell
s = "labuladong world hello"
```

这样，就实现了原地反转所有单词顺序的目的。

我讲这道题的目的是什么呢？

**旨在说明，有时候咱们拍脑袋的常规思维，在计算机看来可能并不是最优雅的；但是计算机觉得最优雅的思维，对咱们来说却不那么直观**。也许这就是算法的魅力所在吧。

回到之前说的顺时针旋转二维矩阵的问题，常规的思路就是去寻找原始坐标和旋转后坐标的映射规律，但我们是否可以让思维跳跃跳跃，尝试把矩阵进行反转、镜像对称等操作，可能会出现新的突破口。

**我们可以先将 `n x n` 矩阵 `matrix` 按照左上到右下的对角线进行镜像对称**：

[![](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/2.jpeg)](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/2.jpeg)

**然后再对矩阵的每一行进行反转**：

[![](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/3.jpeg)](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/3.jpeg)

**发现结果就是 `matrix` 顺时针旋转 90 度的结果**：

[![](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/4.jpeg)](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/4.jpeg)

将上述思路翻译成代码，即可解决本题：

```java
// 将二维矩阵原地顺时针旋转 90 度
public void rotate(int[][] matrix) {
    int n = matrix.length;
    // 先沿对角线镜像对称二维矩阵
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            // swap(matrix[i][j], matrix[j][i]);
            int temp = matrix[i][j];
            matrix[i][j] = matrix[j][i];
            matrix[j][i] = temp;
        }
    }
    // 然后反转二维矩阵的每一行
    for (int[] row : matrix) {
        reverse(row);
    }
}

// 反转一维数组
void reverse(int[] arr) {
    int i = 0, j = arr.length - 1;
    while (j > i) {
        // swap(arr[i], arr[j]);
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}
```

肯定有读者会问，如果没有做过这道题，怎么可能想到这种思路呢？

其实我觉得这个思路还是挺容易想出来的，如果学过线性代数，这道算法题的思路本质就是矩阵变换，肯定可以想出来。

即便没学过线性代数，旋转二维矩阵的难点在于将「行」变成「列」，将「列」变成「行」，而只有按照对角线的对称操作是可以轻松完成这一点的，对称操作之后就很容易发现规律了。

**既然说道这里，我们可以发散一下，如何将矩阵逆时针旋转 90 度呢**？

思路是类似的，只要通过另一条对角线镜像对称矩阵，然后再反转每一行，就得到了逆时针旋转矩阵的结果：

[![](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/5.jpeg)](https://labuladong.github.io/algo/images/%E8%8A%B1%E5%BC%8F%E9%81%8D%E5%8E%86/5.jpeg)

翻译成代码如下：

```java
// 将二维矩阵原地逆时针旋转 90 度
void rotate2(int[][] matrix) {
    int n = matrix.length;
    // 沿左下到右上的对角线镜像对称二维矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            // swap(matrix[i][j], matrix[n-j-1][n-i-1])
            int temp = matrix[i][j];
            matrix[i][j] = matrix[n - j - 1][n - i - 1];
            matrix[n - j - 1][n - i - 1] = temp;
        }
    }
    // 然后反转二维矩阵的每一行
    for (int[] row : matrix) {
        reverse(row);
    }
}

void reverse(int[] arr) { /* 见上文 */}
```

至此，旋转矩阵的问题就解决了。