力扣第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)，在原地修改矩阵，不需要额外空间。