48. 旋转图像

题目描述

给定一个 n × n 的二维矩阵 matrix 表示一个图像。将图像顺时针旋转 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]
]

---

解题思路

要在原地实现顺时针旋转 90 度，我们可以分两步完成：

1. 矩阵转置

• 什么是转置？ 把矩阵的行变为列，例如：

  原始矩阵：
  1  2  3
  4  5  6
  7  8  9
  
  转置后：
  1  4  7
  2  5  8
  3  6  9

• 如何实现？ 遍历矩阵上三角部分（或者下三角部分），交换矩阵中对应的元素：matrix[i][j] 和 matrix[j][i]。

2. 水平翻转

• 什么是水平翻转？ 把矩阵的每一行左右翻转，例如：

  转置后矩阵：
  1  4  7
  2  5  8
  3  6  9
  
  水平翻转后：
  7  4  1
  8  5  2
  9  6  3

• 如何实现？ 遍历矩阵的每一行，将每行的第 i 列和倒数第 i 列的元素交换。

这两步操作可以在不借助额外的矩阵的情况下完成，满足题目要求。

---

代码实现

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Read matrix dimension (n x n)
        int n = scanner.nextInt();

        // Read matrix elements
        int[][] matrix = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = scanner.nextInt();
            }
        }

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

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

        scanner.close();
    }
}

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // 1. 矩阵转置
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // 2. 水平翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
}

---

时间复杂度分析

1. 矩阵转置：

   • 需要遍历矩阵的上三角部分，进行元素交换。
   • 交换次数约为 n²/2，时间复杂度为 O(n²)。

2. 水平翻转：

   • 需要遍历每一行，对每行的前半部分元素进行交换。
   • 交换次数约为 n²/2，时间复杂度为 O(n²)。

总时间复杂度：O(n²)，其中 n 是矩阵的边长。

---

空间复杂度分析

1. 原地操作：
   • 所有操作都在原矩阵上进行，不使用额外的矩阵空间。
2. 临时变量：
   • 仅使用一个临时变量进行元素交换，占用常数空间。

总空间复杂度：O(1)，满足原地旋转的要求。

---

注意事项

1. 边界条件：

   • 如果矩阵为空或者只有一个元素（n = 1），直接返回即可。

2. 原地修改：

   • 确保不借助任何额外存储空间。

3. 矩阵大小：

   • 题目保证是 n × n 矩阵，无需考虑矩阵非方阵的情况。

---