LeetCode中二维数组如何实现旋转矩阵

在LeetCode等编程竞赛平台中，二维数组的旋转矩阵是一个常见的算法问题。这类问题通常要求我们将一个二维数组（矩阵）按照顺时针或逆时针方向旋转90度、180度或270度。本文将详细介绍如何实现二维数组的旋转矩阵，并提供一个具体的代码示例。

1. 问题描述

给定一个 n x n 的二维矩阵 matrix，要求将其顺时针旋转90度。旋转后的矩阵应该直接修改原矩阵，而不是返回一个新的矩阵。

例如，给定矩阵：

1 2 3
4 5 6
7 8 9

旋转90度后应该变为：

7 4 1
8 5 2
9 6 3

2. 解决思路

要实现矩阵的旋转，我们可以采用以下步骤：

1. 转置矩阵：将矩阵的行和列互换。例如，矩阵中的元素 matrix[i][j] 会变成 matrix[j][i]。
2. 反转每一行：将转置后的矩阵的每一行进行反转。

通过这两个步骤，我们可以实现矩阵的顺时针旋转90度。

2.1 转置矩阵

转置矩阵的操作是将矩阵的行和列互换。对于一个 n x n 的矩阵，转置操作可以通过以下代码实现：

for i in range(n):
    for j in range(i, n):
        matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

2.2 反转每一行

转置后的矩阵的每一行需要进行反转。反转操作可以通过以下代码实现：

for i in range(n):
    matrix[i].reverse()

3. 代码实现

结合上述两个步骤，我们可以实现矩阵的顺时针旋转90度。以下是完整的Python代码：

def rotate(matrix):
    n = len(matrix)
    
    # Step 1: Transpose the matrix
    for i in range(n):
        for j in range(i, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    
    # Step 2: Reverse each row
    for i in range(n):
        matrix[i].reverse()

3.1 示例

让我们通过一个示例来验证这个算法。假设我们有以下矩阵：

matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

调用 rotate(matrix) 后，矩阵将变为：

[
    [7, 4, 1],
    [8, 5, 2],
    [9, 6, 3]
]

4. 复杂度分析

• 时间复杂度：转置矩阵的时间复杂度为 O(n^2)，反转每一行的时间复杂度为 O(n)，因此总的时间复杂度为 O(n^2)。
• 空间复杂度：由于我们直接在原矩阵上进行操作，没有使用额外的空间，因此空间复杂度为 O(1)。

5. 其他旋转角度

除了顺时针旋转90度，我们还可以通过类似的方法实现其他角度的旋转：

• 逆时针旋转90度：可以先反转每一行，然后再转置矩阵。
• 旋转180度：可以先将矩阵上下翻转，然后再左右翻转。
• 旋转270度：可以先转置矩阵，然后再反转每一列。

6. 总结

通过转置矩阵和反转每一行的操作，我们可以高效地实现二维数组的旋转矩阵。这种方法不仅简单易懂，而且具有较低的时间和空间复杂度。在实际编程竞赛中，掌握这种技巧可以帮助我们快速解决类似的问题。

希望本文对你理解如何在LeetCode中实现二维数组的旋转矩阵有所帮助！