旋转矩阵

📖 算法简介

旋转矩阵是二维数组操作中的经典问题，在计算机图形学、图像处理、游戏开发等领域有广泛应用。给定一个n×n的二维矩阵，要求将其顺时针旋转90度。这个问题考查对二维数组索引变换的理解，是算法面试中的高频题目。

核心思想：通过数学坐标变换，将原矩阵中每个元素的位置映射到旋转后的新位置。

🎯 问题定义

基本概念

• 旋转矩阵：将二维矩阵按指定角度进行旋转变换
• 顺时针旋转90°：最常见的旋转操作
• 原地旋转：不使用额外空间，在原矩阵上直接修改
• 坐标变换：(i,j) → (j, n-1-i)

示例说明

3×3矩阵旋转

原矩阵:          旋转90°后:
[1,2,3]          [7,4,1]
[4,5,6]    →     [8,5,2]
[7,8,9]          [9,6,3]

4×4矩阵旋转

原矩阵:              旋转90°后:
[ 1, 2, 3, 4]       [13, 9, 5, 1]
[ 5, 6, 7, 8]   →   [14,10, 6, 2]
[ 9,10,11,12]       [15,11, 7, 3]
[13,14,15,16]       [16,12, 8, 4]

数学基础

坐标变换公式

对于n×n矩阵的顺时针90°旋转：

• 原坐标: (i, j)
• 新坐标: (j, n-1-i)

变换矩阵

旋转变换矩阵 R(90°) = [0  -1]
                      [1   0]

🧠 算法原理

方法一：转置 + 水平翻转

这是最直观的方法，分两步完成：

1. 转置矩阵：沿主对角线翻转，(i,j) ↔ (j,i)
2. 水平翻转：沿垂直中轴翻转，(i,j) → (i, n-1-j)

变换过程图解

原矩阵:     转置后:     水平翻转后:
[1,2,3]     [1,4,7]     [7,4,1]
[4,5,6] →   [2,5,8] →   [8,5,2]
[7,8,9]     [3,6,9]     [9,6,3]

方法二：原地旋转（分层处理）

将矩阵看作多个同心正方形层，从外层到内层逐层旋转：

1. 分层：n×n矩阵有⌊n/2⌋层
2. 四点循环：每层中四个对应位置的元素循环交换
3. 逐层处理：从最外层开始，逐层向内处理

分层示意图

4×4矩阵的分层:
┌─────────────┐  ← 第0层
│ ┌─────────┐ │
│ │ ┌─────┐ │ │  ← 第1层
│ │ │  ●  │ │ │
│ │ └─────┘ │ │
│ └─────────┘ │
└─────────────┘

方法三：直接坐标映射

根据坐标变换公式，直接计算每个元素的新位置：

matrix[j][n-1-i] = original[i][j]

💻 代码实现

方法一：转置 + 水平翻转

Java实现

public class RotateMatrix {
    /**
     * 通过转置和水平翻转实现矩阵旋转
     * @param matrix 输入矩阵
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // 第一步：转置矩阵（沿主对角线翻转）
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                // 交换 matrix[i][j] 和 matrix[j][i]
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        
        // 第二步：水平翻转（沿垂直中轴翻转）
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n / 2; j++) {
                // 交换 matrix[i][j] 和 matrix[i][n-1-j]
                int temp = matrix[i][j];
                matrix[i][j] = matrix[i][n - 1 - j];
                matrix[i][n - 1 - j] = temp;
            }
        }
    }
    
    /**
     * 打印矩阵
     * @param matrix 矩阵
     */
    public void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) {
                System.out.printf("%3d ", val);
            }
            System.out.println();
        }
        System.out.println();
    }
}

Python实现

from typing import List

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        通过转置和水平翻转实现矩阵旋转
        
        Args:
            matrix: 输入矩阵，原地修改
        """
        n = len(matrix)
        
        # 第一步：转置矩阵
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 第二步：水平翻转
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
    
    def print_matrix(self, matrix: List[List[int]]) -> None:
        """
        打印矩阵
        
        Args:
            matrix: 要打印的矩阵
        """
        for row in matrix:
            print(' '.join(f'{val:3d}' for val in row))
        print()

方法二：原地旋转（分层处理）

Java实现

public class RotateMatrixInPlace {
    /**
     * 原地旋转矩阵（分层处理）
     * @param matrix 输入矩阵
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        
        // 处理每一层
        for (int layer = 0; layer < n / 2; layer++) {
            int first = layer;
            int last = n - 1 - layer;
            
            // 处理当前层的每个位置
            for (int i = first; i < last; i++) {
                int offset = i - first;
                
                // 保存top元素
                int top = matrix[first][i];
                
                // left -> top
                matrix[first][i] = matrix[last - offset][first];
                
                // bottom -> left
                matrix[last - offset][first] = matrix[last][last - offset];
                
                // right -> bottom
                matrix[last][last - offset] = matrix[i][last];
                
                // top -> right
                matrix[i][last] = top;
            }
        }
    }
}

Python实现

class SolutionInPlace:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        原地旋转矩阵（分层处理）
        
        Args:
            matrix: 输入矩阵，原地修改
        """
        n = len(matrix)
        
        # 处理每一层
        for layer in range(n // 2):
            first = layer
            last = n - 1 - layer
            
            # 处理当前层的每个位置
            for i in range(first, last):
                offset = i - first
                
                # 四个位置的循环交换
                # 保存top
                top = matrix[first][i]
                
                # left -> top
                matrix[first][i] = matrix[last - offset][first]
                
                # bottom -> left
                matrix[last - offset][first] = matrix[last][last - offset]
                
                # right -> bottom
                matrix[last][last - offset] = matrix[i][last]
                
                # top -> right
                matrix[i][last] = top

方法三：使用辅助数组

class SolutionWithAuxArray:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        使用辅助数组实现矩阵旋转
        
        Args:
            matrix: 输入矩阵，原地修改
        """
        n = len(matrix)
        # 创建辅助数组
        rotated = [[0] * n for _ in range(n)]
        
        # 根据坐标变换公式填充新矩阵
        for i in range(n):
            for j in range(n):
                rotated[j][n - 1 - i] = matrix[i][j]
        
        # 将结果复制回原矩阵
        for i in range(n):
            for j in range(n):
                matrix[i][j] = rotated[i][j]

测试代码

def test_rotate_matrix():
    """
    测试旋转矩阵算法
    """
    solution = Solution()
    
    # 测试用例1: 3x3矩阵
    matrix1 = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    print("原矩阵:")
    solution.print_matrix(matrix1)
    
    solution.rotate(matrix1)
    print("旋转后:")
    solution.print_matrix(matrix1)
    
    # 测试用例2: 4x4矩阵
    matrix2 = [
        [1,  2,  3,  4],
        [5,  6,  7,  8],
        [9,  10, 11, 12],
        [13, 14, 15, 16]
    ]
    print("原矩阵:")
    solution.print_matrix(matrix2)
    
    solution.rotate(matrix2)
    print("旋转后:")
    solution.print_matrix(matrix2)
    
    # 测试用例3: 1x1矩阵
    matrix3 = [[1]]
    print("原矩阵:")
    solution.print_matrix(matrix3)
    
    solution.rotate(matrix3)
    print("旋转后:")
    solution.print_matrix(matrix3)

if __name__ == "__main__":
    test_rotate_matrix()

📊 复杂度分析

时间复杂度

方法	时间复杂度	说明
转置+翻转	O(n²)	需要遍历矩阵两次
原地旋转	O(n²)	每个元素访问一次
辅助数组	O(n²)	遍历矩阵两次（读取+写入）

空间复杂度

方法	空间复杂度	说明
转置+翻转	O(1)	只使用常数额外空间
原地旋转	O(1)	只使用常数额外空间
辅助数组	O(n²)	需要额外的n×n矩阵

性能对比

import time
import random

def performance_test():
    """
    性能测试：比较不同实现方法
    """
    sizes = [10, 50, 100, 200]
    
    for n in sizes:
        # 生成测试矩阵
        matrix = [[random.randint(1, 100) for _ in range(n)] for _ in range(n)]
        
        print(f"\n矩阵大小: {n}×{n}")
        
        # 测试转置+翻转方法
        test_matrix = [row[:] for row in matrix]  # 深拷贝
        start = time.time()
        Solution().rotate(test_matrix)
        time1 = time.time() - start
        
        # 测试原地旋转方法
        test_matrix = [row[:] for row in matrix]  # 深拷贝
        start = time.time()
        SolutionInPlace().rotate(test_matrix)
        time2 = time.time() - start
        
        # 测试辅助数组方法
        test_matrix = [row[:] for row in matrix]  # 深拷贝
        start = time.time()
        SolutionWithAuxArray().rotate(test_matrix)
        time3 = time.time() - start
        
        print(f"转置+翻转: {time1:.6f}s")
        print(f"原地旋转: {time2:.6f}s")
        print(f"辅助数组: {time3:.6f}s")

if __name__ == "__main__":
    performance_test()

🚀 算法优化

1. 缓存友好的访问模式

class OptimizedSolution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        缓存友好的矩阵旋转
        """
        n = len(matrix)
        
        # 按块处理，提高缓存命中率
        block_size = min(64, n)  # 根据缓存行大小调整
        
        # 分块转置
        for i in range(0, n, block_size):
            for j in range(i, n, block_size):
                # 处理当前块
                for ii in range(i, min(i + block_size, n)):
                    for jj in range(max(j, ii), min(j + block_size, n)):
                        matrix[ii][jj], matrix[jj][ii] = matrix[jj][ii], matrix[ii][jj]
        
        # 水平翻转
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]

2. 并行化处理

import concurrent.futures
from typing import List

class ParallelSolution:
    def rotate_parallel(self, matrix: List[List[int]]) -> None:
        """
        并行化矩阵旋转
        """
        n = len(matrix)
        
        def transpose_block(start_row, end_row):
            """转置指定行范围的块"""
            for i in range(start_row, end_row):
                for j in range(i, n):
                    matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        def flip_block(start_row, end_row):
            """水平翻转指定行范围的块"""
            for i in range(start_row, end_row):
                for j in range(n // 2):
                    matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
        
        # 计算线程数
        num_threads = min(4, n)  # 最多4个线程
        chunk_size = n // num_threads
        
        # 并行转置
        with concurrent.futures.ThreadPoolExecutor(max_workers=num_threads) as executor:
            futures = []
            for i in range(num_threads):
                start = i * chunk_size
                end = n if i == num_threads - 1 else (i + 1) * chunk_size
                futures.append(executor.submit(transpose_block, start, end))
            
            # 等待所有任务完成
            concurrent.futures.wait(futures)
        
        # 并行水平翻转
        with concurrent.futures.ThreadPoolExecutor(max_workers=num_threads) as executor:
            futures = []
            for i in range(num_threads):
                start = i * chunk_size
                end = n if i == num_threads - 1 else (i + 1) * chunk_size
                futures.append(executor.submit(flip_block, start, end))
            
            # 等待所有任务完成
            concurrent.futures.wait(futures)

🔄 变种问题

1. 逆时针旋转90度

class CounterClockwiseRotation:
    def rotate_counter_clockwise(self, matrix: List[List[int]]) -> None:
        """
        逆时针旋转90度
        坐标变换：(i,j) -> (n-1-j, i)
        """
        n = len(matrix)
        
        # 方法1：转置 + 垂直翻转
        # 转置
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 垂直翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]

2. 旋转180度

class Rotate180:
    def rotate_180(self, matrix: List[List[int]]) -> None:
        """
        旋转180度
        坐标变换：(i,j) -> (n-1-i, n-1-j)
        """
        n = len(matrix)
        
        # 方法1：两次90度旋转
        self.rotate_90(matrix)
        self.rotate_90(matrix)
    
    def rotate_180_direct(self, matrix: List[List[int]]) -> None:
        """
        直接180度旋转（更高效）
        """
        n = len(matrix)
        
        # 只需要交换对角位置的元素
        for i in range(n):
            for j in range(n):
                if i * n + j < (n - 1 - i) * n + (n - 1 - j):
                    matrix[i][j], matrix[n - 1 - i][n - 1 - j] = \
                        matrix[n - 1 - i][n - 1 - j], matrix[i][j]

3. 任意角度旋转

import math
from typing import List, Tuple

class ArbitraryRotation:
    def rotate_arbitrary(self, matrix: List[List[int]], angle: float) -> List[List[int]]:
        """
        任意角度旋转（需要新矩阵存储结果）
        
        Args:
            matrix: 输入矩阵
            angle: 旋转角度（弧度）
        
        Returns:
            旋转后的矩阵
        """
        n = len(matrix)
        
        # 计算旋转后矩阵的大小
        cos_a = abs(math.cos(angle))
        sin_a = abs(math.sin(angle))
        new_size = int(n * (cos_a + sin_a)) + 1
        
        # 创建新矩阵
        result = [[0] * new_size for _ in range(new_size)]
        
        # 计算中心点
        center_old = (n - 1) / 2
        center_new = (new_size - 1) / 2
        
        # 旋转变换
        cos_angle = math.cos(angle)
        sin_angle = math.sin(angle)
        
        for i in range(n):
            for j in range(n):
                # 相对于中心的坐标
                x = i - center_old
                y = j - center_old
                
                # 旋转变换
                new_x = x * cos_angle - y * sin_angle
                new_y = x * sin_angle + y * cos_angle
                
                # 转换回矩阵坐标
                new_i = int(new_x + center_new)
                new_j = int(new_y + center_new)
                
                # 边界检查
                if 0 <= new_i < new_size and 0 <= new_j < new_size:
                    result[new_i][new_j] = matrix[i][j]
        
        return result

4. 矩形矩阵旋转

class RectangleRotation:
    def rotate_rectangle(self, matrix: List[List[int]]) -> List[List[int]]:
        """
        旋转m×n矩形矩阵（90度顺时针）
        结果是n×m矩阵
        
        Args:
            matrix: m×n矩阵
        
        Returns:
            n×m旋转后矩阵
        """
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        
        # 创建n×m的结果矩阵
        result = [[0] * m for _ in range(n)]
        
        # 坐标变换：(i,j) -> (j, m-1-i)
        for i in range(m):
            for j in range(n):
                result[j][m - 1 - i] = matrix[i][j]
        
        return result

5. 多次旋转优化

class MultipleRotation:
    def rotate_multiple(self, matrix: List[List[int]], times: int) -> None:
        """
        多次旋转优化（利用周期性）
        
        Args:
            matrix: 输入矩阵
            times: 旋转次数（每次90度）
        """
        # 利用旋转的周期性：4次90度旋转回到原状态
        times = times % 4
        
        if times == 0:
            return  # 不需要旋转
        elif times == 1:
            self.rotate_90(matrix)
        elif times == 2:
            self.rotate_180(matrix)
        elif times == 3:
            self.rotate_270(matrix)  # 等价于逆时针90度
    
    def rotate_90(self, matrix: List[List[int]]) -> None:
        """顺时针90度旋转"""
        n = len(matrix)
        # 转置 + 水平翻转
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
    
    def rotate_180(self, matrix: List[List[int]]) -> None:
        """180度旋转"""
        n = len(matrix)
        for i in range(n):
            for j in range(n):
                if i * n + j < (n - 1 - i) * n + (n - 1 - j):
                    matrix[i][j], matrix[n - 1 - i][n - 1 - j] = \
                        matrix[n - 1 - i][n - 1 - j], matrix[i][j]
    
    def rotate_270(self, matrix: List[List[int]]) -> None:
        """顺时针270度旋转（等价于逆时针90度）"""
        n = len(matrix)
        # 转置 + 垂直翻转
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]

🎯 实际应用场景

1. 图像处理

import numpy as np
from PIL import Image

class ImageRotation:
    def rotate_image(self, image_path: str, angle: int) -> None:
        """
        图像旋转应用
        
        Args:
            image_path: 图像文件路径
            angle: 旋转角度（90, 180, 270）
        """
        # 读取图像
        img = Image.open(image_path)
        img_array = np.array(img)
        
        # 根据角度选择旋转方法
        if angle == 90:
            rotated = self.rotate_90_image(img_array)
        elif angle == 180:
            rotated = self.rotate_180_image(img_array)
        elif angle == 270:
            rotated = self.rotate_270_image(img_array)
        else:
            raise ValueError("只支持90, 180, 270度旋转")
        
        # 保存旋转后的图像
        rotated_img = Image.fromarray(rotated)
        base_name = image_path.rsplit('.', 1)[0]
        extension = image_path.rsplit('.', 1)[1]
        rotated_img.save(f"{base_name}_rotated_{angle}.{extension}")
    
    def rotate_90_image(self, img_array: np.ndarray) -> np.ndarray:
        """图像90度旋转"""
        return np.rot90(img_array, k=-1)  # 顺时针90度
    
    def rotate_180_image(self, img_array: np.ndarray) -> np.ndarray:
        """图像180度旋转"""
        return np.rot90(img_array, k=2)
    
    def rotate_270_image(self, img_array: np.ndarray) -> np.ndarray:
        """图像270度旋转"""
        return np.rot90(img_array, k=1)  # 逆时针90度

2. 游戏开发

class GameBoard:
    def __init__(self, size: int):
        self.size = size
        self.board = [[0] * size for _ in range(size)]
    
    def rotate_board(self) -> None:
        """
        游戏棋盘旋转（如俄罗斯方块）
        """
        # 使用转置+翻转方法
        n = self.size
        
        # 转置
        for i in range(n):
            for j in range(i, n):
                self.board[i][j], self.board[j][i] = self.board[j][i], self.board[i][j]
        
        # 水平翻转
        for i in range(n):
            for j in range(n // 2):
                self.board[i][j], self.board[i][n - 1 - j] = \
                    self.board[i][n - 1 - j], self.board[i][j]
    
    def place_piece(self, piece: List[List[int]], row: int, col: int) -> bool:
        """
        在棋盘上放置游戏块
        
        Args:
            piece: 游戏块矩阵
            row: 放置行位置
            col: 放置列位置
        
        Returns:
            是否成功放置
        """
        piece_size = len(piece)
        
        # 检查边界
        if row + piece_size > self.size or col + piece_size > self.size:
            return False
        
        # 检查冲突
        for i in range(piece_size):
            for j in range(piece_size):
                if piece[i][j] and self.board[row + i][col + j]:
                    return False
        
        # 放置游戏块
        for i in range(piece_size):
            for j in range(piece_size):
                if piece[i][j]:
                    self.board[row + i][col + j] = piece[i][j]
        
        return True

3. 数据可视化

import matplotlib.pyplot as plt
import numpy as np

class DataVisualization:
    def rotate_heatmap(self, data: List[List[float]], angle: int) -> None:
        """
        旋转热力图数据
        
        Args:
            data: 二维数据
            angle: 旋转角度
        """
        data_array = np.array(data)
        
        # 根据角度旋转数据
        if angle == 90:
            rotated_data = np.rot90(data_array, k=-1)
        elif angle == 180:
            rotated_data = np.rot90(data_array, k=2)
        elif angle == 270:
            rotated_data = np.rot90(data_array, k=1)
        else:
            rotated_data = data_array
        
        # 创建子图
        fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12, 5))
        
        # 原始数据热力图
        im1 = ax1.imshow(data_array, cmap='viridis')
        ax1.set_title('原始数据')
        plt.colorbar(im1, ax=ax1)
        
        # 旋转后数据热力图
        im2 = ax2.imshow(rotated_data, cmap='viridis')
        ax2.set_title(f'旋转{angle}度后')
        plt.colorbar(im2, ax=ax2)
        
        plt.tight_layout()
        plt.show()

📝 常见面试题

1. LeetCode 48: 旋转图像

题目：给定一个n×n的二维矩阵表示一个图像，将图像顺时针旋转90度。要求原地旋转图像。

解题要点：

• 必须原地旋转，不能使用额外的矩阵
• 理解坐标变换规律
• 掌握转置+翻转的方法

标准解法：

class LeetCode48:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        LeetCode 48: 旋转图像
        
        Args:
            matrix: n×n矩阵，原地修改
        """
        n = len(matrix)
        
        # 转置矩阵
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 水平翻转
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]

2. 相关变种题目

螺旋矩阵（LeetCode 54）

class SpiralMatrix:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """
        螺旋遍历矩阵
        """
        if not matrix or not matrix[0]:
            return []
        
        m, n = len(matrix), len(matrix[0])
        result = []
        
        top, bottom = 0, m - 1
        left, right = 0, n - 1
        
        while top <= bottom and left <= right:
            # 从左到右
            for j in range(left, right + 1):
                result.append(matrix[top][j])
            top += 1
            
            # 从上到下
            for i in range(top, bottom + 1):
                result.append(matrix[i][right])
            right -= 1
            
            # 从右到左
            if top <= bottom:
                for j in range(right, left - 1, -1):
                    result.append(matrix[bottom][j])
                bottom -= 1
            
            # 从下到上
            if left <= right:
                for i in range(bottom, top - 1, -1):
                    result.append(matrix[i][left])
                left += 1
        
        return result

矩阵置零（LeetCode 73）

class SetMatrixZeroes:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        矩阵置零：如果一个元素为0，则将其所在行和列的所有元素都设为0
        """
        m, n = len(matrix), len(matrix[0])
        
        # 使用第一行和第一列作为标记
        first_row_zero = any(matrix[0][j] == 0 for j in range(n))
        first_col_zero = any(matrix[i][0] == 0 for i in range(m))
        
        # 标记需要置零的行和列
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0
        
        # 根据标记置零
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][0] == 0 or matrix[0][j] == 0:
                    matrix[i][j] = 0
        
        # 处理第一行
        if first_row_zero:
            for j in range(n):
                matrix[0][j] = 0
        
        # 处理第一列
        if first_col_zero:
            for i in range(m):
                matrix[i][0] = 0

3. 解题模板

class RotationTemplate:
    """
    旋转矩阵解题模板
    """
    
    def rotate_90_clockwise(self, matrix: List[List[int]]) -> None:
        """
        顺时针90度旋转模板
        """
        n = len(matrix)
        
        # 方法1：转置 + 水平翻转
        # 转置
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 水平翻转
        for i in range(n):
            for j in range(n // 2):
                matrix[i][j], matrix[i][n - 1 - j] = matrix[i][n - 1 - j], matrix[i][j]
    
    def rotate_90_counterclockwise(self, matrix: List[List[int]]) -> None:
        """
        逆时针90度旋转模板
        """
        n = len(matrix)
        
        # 转置 + 垂直翻转
        # 转置
        for i in range(n):
            for j in range(i, n):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        
        # 垂直翻转
        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]
    
    def rotate_in_place(self, matrix: List[List[int]]) -> None:
        """
        原地旋转模板（分层处理）
        """
        n = len(matrix)
        
        for layer in range(n // 2):
            first = layer
            last = n - 1 - layer
            
            for i in range(first, last):
                offset = i - first
                
                # 四个位置的循环交换
                top = matrix[first][i]
                
                # left -> top
                matrix[first][i] = matrix[last - offset][first]
                
                # bottom -> left
                matrix[last - offset][first] = matrix[last][last - offset]
                
                # right -> bottom
                matrix[last][last - offset] = matrix[i][last]
                
                # top -> right
                matrix[i][last] = top

📈 性能测试与分析

import time
import random
import matplotlib.pyplot as plt

class PerformanceAnalysis:
    def __init__(self):
        self.solution1 = Solution()  # 转置+翻转
        self.solution2 = SolutionInPlace()  # 原地旋转
        self.solution3 = SolutionWithAuxArray()  # 辅助数组
    
    def generate_test_matrix(self, n: int) -> List[List[int]]:
        """生成测试矩阵"""
        return [[random.randint(1, 100) for _ in range(n)] for _ in range(n)]
    
    def benchmark_methods(self, sizes: List[int]) -> dict:
        """
        性能基准测试
        
        Args:
            sizes: 测试的矩阵大小列表
        
        Returns:
            性能测试结果
        """
        results = {
            'sizes': sizes,
            'transpose_flip': [],
            'in_place': [],
            'aux_array': []
        }
        
        for n in sizes:
            print(f"测试矩阵大小: {n}×{n}")
            
            # 生成测试数据
            original_matrix = self.generate_test_matrix(n)
            
            # 测试转置+翻转方法
            test_matrix = [row[:] for row in original_matrix]
            start_time = time.time()
            self.solution1.rotate(test_matrix)
            time1 = time.time() - start_time
            results['transpose_flip'].append(time1)
            
            # 测试原地旋转方法
            test_matrix = [row[:] for row in original_matrix]
            start_time = time.time()
            self.solution2.rotate(test_matrix)
            time2 = time.time() - start_time
            results['in_place'].append(time2)
            
            # 测试辅助数组方法
            test_matrix = [row[:] for row in original_matrix]
            start_time = time.time()
            self.solution3.rotate(test_matrix)
            time3 = time.time() - start_time
            results['aux_array'].append(time3)
            
            print(f"  转置+翻转: {time1:.6f}s")
            print(f"  原地旋转: {time2:.6f}s")
            print(f"  辅助数组: {time3:.6f}s")
            print()
        
        return results
    
    def plot_performance(self, results: dict) -> None:
        """
        绘制性能对比图
        
        Args:
            results: 性能测试结果
        """
        plt.figure(figsize=(12, 8))
        
        plt.plot(results['sizes'], results['transpose_flip'], 
                'o-', label='转置+翻转', linewidth=2, markersize=6)
        plt.plot(results['sizes'], results['in_place'], 
                's-', label='原地旋转', linewidth=2, markersize=6)
        plt.plot(results['sizes'], results['aux_array'], 
                '^-', label='辅助数组', linewidth=2, markersize=6)
        
        plt.xlabel('矩阵大小 (n×n)', fontsize=12)
        plt.ylabel('执行时间 (秒)', fontsize=12)
        plt.title('旋转矩阵算法性能对比', fontsize=14)
        plt.legend(fontsize=11)
        plt.grid(True, alpha=0.3)
        
        # 设置对数坐标（如果需要）
        plt.yscale('log')
        
        plt.tight_layout()
        plt.show()
    
    def memory_usage_analysis(self, n: int) -> None:
        """
        内存使用分析
        
        Args:
            n: 矩阵大小
        """
        import tracemalloc
        
        matrix = self.generate_test_matrix(n)
        
        print(f"内存使用分析 (矩阵大小: {n}×{n})")
        print(f"原始矩阵内存: {n * n * 4} 字节 (假设int为4字节)")
        
        # 测试转置+翻转方法的内存使用
        tracemalloc.start()
        test_matrix = [row[:] for row in matrix]
        self.solution1.rotate(test_matrix)
        current, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()
        print(f"转置+翻转方法 - 当前内存: {current} 字节, 峰值内存: {peak} 字节")
        
        # 测试辅助数组方法的内存使用
        tracemalloc.start()
        test_matrix = [row[:] for row in matrix]
        self.solution3.rotate(test_matrix)
        current, peak = tracemalloc.get_traced_memory()
        tracemalloc.stop()
        print(f"辅助数组方法 - 当前内存: {current} 字节, 峰值内存: {peak} 字节")

def run_performance_test():
    """
    运行性能测试
    """
    analyzer = PerformanceAnalysis()
    
    # 测试不同大小的矩阵
    sizes = [10, 50, 100, 200, 500, 1000]
    results = analyzer.benchmark_methods(sizes)
    
    # 绘制性能对比图
    analyzer.plot_performance(results)
    
    # 内存使用分析
    analyzer.memory_usage_analysis(1000)

if __name__ == "__main__":
    run_performance_test()

🎓 学习总结

核心要点

1. 理解坐标变换：掌握(i,j) → (j, n-1-i)的变换规律
2. 两种主要方法：转置+翻转 vs 原地旋转
3. 空间复杂度优化：优先选择O(1)空间的方法
4. 边界条件处理：注意1×1矩阵和空矩阵的情况
5. 扩展应用：理解在图像处理、游戏开发中的应用

解题技巧

1. 画图理解：通过小矩阵画图理解旋转规律
2. 分步实现：先实现简单方法，再优化空间复杂度
3. 验证正确性：用小矩阵验证算法正确性
4. 性能考虑：根据实际需求选择合适的实现方法

常见错误

1. 坐标变换错误：混淆行列索引的变换关系
2. 边界处理不当：忽略矩阵大小为1或0的情况
3. 原地修改问题：在原地旋转时数据覆盖
4. 内存泄漏：在大矩阵处理时忘记释放临时空间

扩展学习

• 三维矩阵旋转
• 图像的仿射变换
• 计算机图形学中的变换矩阵
• 并行算法优化
• GPU加速的矩阵运算

实践建议

1. 从简单开始：先掌握基本的90度旋转
2. 理解数学原理：深入理解坐标变换的数学基础
3. 多种实现：掌握不同的实现方法及其适用场景
4. 性能优化：学习缓存友好和并行化的优化技巧
5. 实际应用：结合图像处理等实际场景练习

---

总结：旋转矩阵是一个看似简单但内涵丰富的算法问题。通过学习这个问题，不仅可以掌握二维数组的操作技巧，还能深入理解坐标变换的数学原理。这些知识在计算机图形学、图像处理、游戏开发等领域都有重要应用价值。掌握多种实现方法和优化技巧，能够在不同场景下选择最合适的解决方案。