力扣第48题“旋转图像”

题目描述

给定一个 n × n 的二维矩阵 matrix，将其原地顺时针旋转 90 度。

示例：

输入: matrix = [[1, 2, 3],[4, 5, 6],[7, 8, 9]
]
输出: [[7, 4, 1],[8, 5, 2],[9, 6, 3]
]

解题思路

要将矩阵顺时针旋转 90 度，可以分为以下两个步骤：

1. 矩阵转置：将矩阵的行列互换，使 matrix[i][j] 和 matrix[j][i] 交换。
2. 水平翻转每一行：对于每一行，将左右两边的元素交换，使得第 i 行的第 j 个元素和第 n-1-j 个元素交换。

通过以上步骤，原矩阵将被顺时针旋转 90 度。

代码实现

以下是 C 语言实现和逐行解释。

#include <stdio.h>void rotate(int** matrix, int matrixSize, int* matrixColSize) {// 1. 转置矩阵for (int i = 0; i < matrixSize; i++) {for (int j = i + 1; j < matrixSize; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}}// 2. 水平翻转每一行for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixSize / 2; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[i][matrixSize - 1 - j];matrix[i][matrixSize - 1 - j] = temp;}}
}// 测试代码
int main() {int n = 3;int* matrix[] = {(int[]){1, 2, 3},(int[]){4, 5, 6},(int[]){7, 8, 9}};rotate(matrix, n, NULL);printf("旋转后的矩阵：\n");for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {printf("%d ", matrix[i][j]);}printf("\n");}return 0;
}

代码解析

1. 矩阵转置：

   for (int i = 0; i < matrixSize; i++) {for (int j = i + 1; j < matrixSize; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[j][i];matrix[j][i] = temp;}
   }
   

   • 通过嵌套循环，交换 matrix[i][j] 和 matrix[j][i]，将矩阵进行转置。

2. 水平翻转每一行：

   for (int i = 0; i < matrixSize; i++) {for (int j = 0; j < matrixSize / 2; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[i][matrixSize - 1 - j];matrix[i][matrixSize - 1 - j] = temp;}
   }
   

   • 遍历每一行，将两端的元素交换，从而实现行的水平翻转。

3. 测试代码：

   • 初始化一个 3 × 3 的矩阵，并调用 rotate 函数进行旋转。
   • 输出旋转后的矩阵，验证结果是否正确。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是矩阵的边长。转置和水平翻转各需 O(n^2) 的时间。
• 空间复杂度：O(1)，在原地修改矩阵，不需要额外空间。