深入解析：如何原地逆时针旋转方阵 90 度——从原理到最优解

2026-02-02 00:51:51 0条评论 1次阅读 0人点赞

在算法面试和实际开发中，矩阵操作是一个非常经典的话题。今天，我们将深入探讨一个看似简单却暗藏玄机的问题：如何在不分配额外二维数组（即原地操作）的情况下，将一个方阵逆时针旋转 90 度？

这不仅是一个关于数组索引的练习，更是考察我们空间思维能力和代码优化技巧的绝佳案例。我们将从最直观的暴力解法开始，逐步探索出实现原地旋转的最优路径。

目录

  • [核心挑战与解题思路]
  • [朴素方法] 使用额外空间 – O(n²) 时间和 O(n²) 空间
  • [进阶思路] 原地旋转的数学原理
  • [期望方法 1] 分层处理与循环交换 – O(n²) 时间和 O(1) 空间
  • [期望方法 2] 先转置后反转 – O(n²) 时间和 O(1) 空间
  • [实战建议与常见陷阱]

核心挑战与解题思路

首先，我们需要明确原地的含义。这意味着我们不能简单地创建一个新的矩阵，把数据搬运过去然后返回。我们必须在现有的矩阵内存空间内，通过交换元素的位置来完成旋转。

让我们先通过一个简单的例子来理解“逆时针旋转 90 度”的直观效果。假设我们有一个 3×3 的矩阵：

输入：
[[1, 2, 3],

[4, 5, 6],

[7, 8, 9]]
输出：
[[3, 6, 9],

[2, 5, 8],

[1, 4, 7]]

观察这个变化，你能发现规律吗？

  • 原矩阵的第一行 [1, 2, 3] 变成了新矩阵的第一列（从下往上，即逆序）。
  • 原矩阵的最后一列 [3, 6, 9] 变成了新矩阵的第一行（从左往右）。

核心规律：对于矩阵中任意一个位于 INLINECODEebbbd789 的元素，旋转 90 度逆时针后，它的新位置将变成 INLINECODEc4a2da7c。这里 n 是矩阵的维度（行数或列数）。这个公式是我们解决所有后续问题的基础。

[朴素方法] 使用额外空间 – O(n²) 时间和 O(n²) 空间

当我们面对复杂问题时，最有效的策略往往是先让它跑起来。最直观的方法是创建一个新的临时矩阵，按照我们刚才推导出的坐标映射规则，把旧矩阵的元素一个个放到新位置上，最后再把新矩阵的内容复制回旧矩阵。

算法思路：

  • 创建一个与原矩阵大小相同的临时矩阵 res。
  • 遍历原矩阵的每一个元素 mat[i][j]。
  • 根据公式将其赋值给 res[n - 1 - j][i]。
  • 最后将 INLINECODE6c5b3fc0 的内容复制回 INLINECODE54f3196f。

这种方法的时间复杂度是 O(n²)，因为我们要遍历所有元素。虽然空间复杂度也是 O(n²)，但在某些允许使用辅助空间的场景下，这是最不容易出错的写法。

#### C++ 实现 (朴素方法)

#include 
#include 
using namespace std;

void rotateMatrix(vector<vector>& mat) {
    int n = mat.size();
    // 创建一个临时矩阵用于存储旋转后的结果
    vector<vector> res(n, vector(n));
  
    // 核心逻辑：将 mat[i][j] 移动到 res[n - j - 1][i]
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            res[n - j - 1][i] = mat[i][j];
        }
    }

    // 将结果复制回原矩阵，以满足“修改原矩阵”的要求
    mat = res;
}

int main() {
    vector<vector> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    rotateMatrix(mat);

    for (auto& row : mat) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << endl;
    }
    return 0;
}

#### Java 实现 (朴素方法)

import java.util.Arrays;

class MatrixRotation {
    static void rotateMatrix(int[][] mat) {
        int n = mat.length;
        int[][] res = new int[n][n];

        // 将矩阵逆时针旋转 90 度
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                // 目标位置计算
                res[n - j - 1][i] = mat[i][j];
            }
        }

        // 将旋转后的矩阵复制回原矩阵
        for (int i = 0; i < n; i++) {
            System.arraycopy(res[i], 0, mat[i], 0, n);
        }
    }

    public static void main(String[] args) {
        int[][] mat = {
            {1, 2, 3},
            {4, 5, 6},
            {7, 8, 9}
        };

        rotateMatrix(mat);

        // 打印结果
        for (int[] row : mat) {
            System.out.println(Arrays.toString(row));
        }
    }
}

虽然这种方法很简单，但在面试中，面试官通常会紧接着追问：“我们能不能优化空间复杂度，做到原地旋转？” 让我们来看看如何实现。

[进阶思路] 原地旋转的数学原理

要实现原地旋转，我们就要利用交换来代替额外的存储空间。

想象一下，矩阵是由一层一层组成的“正方形环”。

  • 最外层是一个大正方形环。
  • 里面一层是小正方形环。
  • …直到中心。

对于每一个环，我们可以将其元素分为四组（或四个边）。旋转 90 度本质上就是把这四组元素进行轮转。

具体来说，对于位置 (i, j) 的元素，在逆时针旋转中，它涉及到四个位置的循环移动：

  • 上边 -> 左边
  • 左边 -> 下边
  • 下边 -> 右边
  • 右边 -> 上边

我们可以引入一个临时变量 INLINECODE5e05d7e1，保存其中一个元素，然后像传递接力棒一样，依次移动这三个元素，最后把 INLINECODE1200d673 放入正确的位置。这样，一次操作就能完成四个位置的旋转，而不需要额外的 O(n²) 空间。

[期望方法 1] 形成环 – O(n²) 时间和 O(1) 空间

这种方法也被称为分层旋转法。我们将问题分解为处理每一层“环”。

步骤详解：

  • 按层处理：外层循环变量 INLINECODE9223836f 从 0 到 INLINECODE72443923，代表当前处理的是第几层。
  • 按元素处理：内层循环变量 INLINECODE0448d282 从 INLINECODE51d7342e 到 n - i - 2，代表当前层中需要旋转的元素（注意：每层最后一个元素会由前面的操作自动归位，所以不需要遍历到头）。
  • 四元素交换：

– 保存 INLINECODEb90a08c2 到 INLINECODEccb98281。

– 将 INLINECODE67965819 (右边) 移到 INLINECODE1b9fff5a (上边)。

– 将 INLINECODE43326e14 (下边) 移到 INLINECODEb7262f09 (右边)。

– 将 INLINECODE3e982d22 (左边) 移到 INLINECODE4b8b357a (下边)。

– 将 INLINECODEd63f74f2 (上边) 移到 INLINECODE187ee5aa (左边)。

#### Python 实现 (分层交换法)

def rotate_matrix_swap(mat):
    n = len(mat)
    # 遍历矩阵的层数
    for i in range(n // 2):
        # 遍历当前层的元素
        # 注意：这里只需要处理当前行除去最后一个元素的部分
        for j in range(i, n - i - 1):
            # 保存当前层的第一个元素
            temp = mat[i][j]
            
            # 将右边的元素移动到上边
            mat[i][j] = mat[j][n - 1 - i]
            
            # 将下边的元素移动到右边
            mat[j][n - 1 - i] = mat[n - 1 - i][n - 1 - j]
            
            # 将左边的元素移动到下边
            mat[n - 1 - i][n - 1 - j] = mat[n - 1 - j][i]
            
            # 将保存的临时元素移动到左边
            mat[n - 1 - j][i] = temp

# 测试代码
if __name__ == "__main__":
    matrix = [
        [1, 2, 3],
        [4, 5, 6],
        [7, 8, 9]
    ]
    rotate_matrix_swap(matrix)
    for row in matrix:
        print(row)

这种方法非常高效，因为它完全利用了自身空间。但是，正如你在代码中看到的，索引计算非常繁琐，很容易写错。有没有一种更符合直觉、更不容易出错的方法呢？答案是肯定的。

[期望方法 2] 反转行和转置 – O(n²) 时间和 O(1) 空间

这是最推荐的写法，因为它把复杂的旋转操作拆解成了两个简单且标准的矩阵操作。我们通常使用“转置”配合“翻转”来实现旋转。

对于逆时针 90 度旋转，操作顺序如下：

  • 反转每一行（左右翻转）。
  • 求转置（将行变成列）。

或者，你也可以选择：

  • 求转置。
  • 反转每一列（上下翻转）。

这两种组合都能达到逆时针旋转 90 度的效果。我们采用第一种组合（先反转行，后转置），因为它通常只需要写两个简单的辅助函数。

为什么这样做有效？

  • 反转行：改变了行的顺序，例如 INLINECODE9fc3a9d3 变成了 INLINECODE5e65594a。这模拟了“左右颠倒”。
  • 转置：交换了行和列 (INLINECODE04852f8c INLINECODEdfaadf5b)。在反转的基础上进行转置，刚好完成了逆时针 90 度的坐标变换。

#### C++ 实现 (转置与反转法)

#include 
#include 
#include  // 用于 std::reverse
using namespace std;

// 辅助函数：转置矩阵
void transpose(vector<vector>& mat) {
    int n = mat.size();
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) { // 注意：j 从 i 开始，避免重复交换和自我交换
            swap(mat[i][j], mat[j][i]);
        }
    }
}

// 辅助函数：反转每一行
void reverseRows(vector<vector>& mat) {
    int n = mat.size();
    for (int i = 0; i < n; i++) {
        // 使用库函数反转当前行
        reverse(mat[i].begin(), mat[i].end());
    }
}

void rotateMatrix(vector<vector>& mat) {
    // 步骤 1: 反转每一行
    reverseRows(mat);
    
    // 步骤 2: 转置矩阵
    transpose(mat);
}

int main() {
    vector<vector> mat = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
        {13, 14, 15, 16}
    };

    rotateMatrix(mat);

    for (auto& row : mat) {
        for (int x : row) {
            cout << x << ' ';
        }
        cout << endl;
    }
    return 0;
}

#### Python 实现 (转置与反转法 – Pythonic 风格)

Python 的列表推导式和 zip 函数让这个过程极其简洁，非常适合快速原型开发和脚本编写。

def rotate_matrix_pythonic(mat):
    n = len(mat)
    # 1. 反转每一行 (左右翻转)
    # 列表推导式：row[::-1] 表示对每一行进行切片反转
    reversed_rows = [row[::-1] for row in mat]
    
    # 2. 转置矩阵 (行列互换)
    # zip(*reversed_rows) 将所有行解包并按列重新打包
    # list(...) 将 zip 对象转换回列表
    mat[:] = [list(col) for col in zip(*reversed_rows)]

# 测试
mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
rotate_matrix_pythonic(mat)
print(mat) # 输出: [[3, 6, 9], [2, 5, 8], [1, 4, 7]]

[实战建议与常见陷阱]

在实际编码和面试中，有几个细节需要特别注意：

  • 原地更新的陷阱：在 Python 中，如果你直接写 INLINECODE34bbd1fa，这通常只会改变局部变量的引用，而不会修改调用者传入的列表对象。要真正实现“原地修改”，你应该使用切片赋值 INLINECODEac32953b，或者像 C++/Java 那样逐个修改内部元素的值。
  • 转置的索引范围：在手动编写转置函数时，内层循环 INLINECODE6e43b231 必须从 INLINECODEe693e96d 开始，而不是 INLINECODEdbf0658d。如果从 INLINECODE049443a5 开始，你实际上会把矩阵交换两次，导致矩阵变回原样（或者是对角线元素被错误处理）。
  • 顺时针 vs 逆时针：这是一对容易混淆的操作。

– 顺时针 90 度：先转置，再反转每一行（或先反转每一列，再转置）。

– 逆时针 90 度：先反转每一行，再转置（或先转置，再反转每一列）。

记住这个小窍门，你就能轻松应对这两个方向的问题。

总结

在这篇文章中，我们详细探讨了如何原地逆时针旋转方阵 90 度。我们从最基本的坐标映射开始，理解了元素移动的规律，进而学习了两种高效的原地算法：四元循环交换法和转置反转法。

虽然四元交换法在理论上是完美的，但在实际工程中，“先反转行，后转置”的方法因其代码逻辑清晰、不易出错而更受推崇。掌握这些基础操作，不仅能帮助你解决矩阵旋转问题，更能为你处理图像处理、游戏开发等涉及二维数组的复杂场景打下坚实基础。

接下来，你可以尝试挑战一下：如何在不创建新矩阵的情况下，顺时针旋转 180 度？ 思考一下组合使用我们今天学到的技巧吧！

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。如需转载，请注明文章出处豆丁博客和来源网址。https://shluqu.cn/20331.html
点赞
0.00 平均评分 (0% 分数) - 0 票

相关文章美国1G带宽/1T流量高速vps $17.99/年