Rotate Image

Q: 旋转矩阵的时间复杂度和空间复杂度是多少？

旋转一个 n × n 矩阵需要 O(n²) 时间，因为几乎每个值都需要移动一次。转置再反转的方法需要 O(1) 的额外空间。创建旋转后的副本同样需要 O(n²) 时间，但会使用 O(n²) 的额外空间。

Q: 如何将矩阵逆时针旋转？

交换这两个步骤的顺序：先反转每一行，再转置。你也可以先转置，再反转行的顺序。无论哪种方式， (i, j) 处的值最终都会到达 (n-1-j, i) 。

Q: 你能一次移动四个值来旋转矩阵吗？

是的。中心之外的每个值都属于一个包含 4 个单元格的循环： (i, j) 、 (j, n-1-i) 、 (n-1-i, n-1-j) 和 (n-1-j, i) 。按层处理时，将每个循环中的一个值暂存到变量中，再移动其他三个值。它的时间复杂度同样是 O(n²)，空间复杂度是 O(1)，不过需要处理更多索引运算，更容易出错。

中等数组和字符串数学与模拟

+10

给你一个 n × n 的整数网格，每一行是一个列表。将它顺时针旋转四分之一圈并返回。顶行会变成最右侧的一列，第二行会变成它左边的一列，以此类推：位于 (i, j) 的值会移动到 (j, n-1-i)。你可以直接修改网格；返回它。

函数

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: 正方形网格，每行对应一个内层列表
返回值integer-2d-array: 矩阵顺时针旋转了 90 度

约束条件

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

示例

输入: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
输出: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
解释: 第一行 3 7 1 变成最后一列，从上到下读取。第一列 3 9 4 从下到上读取后，变成第一行 [4, 9, 3]。中心值 5 保持不变。

进阶

哪两个原地操作可以将矩阵旋转 180 度？你能否通过一轮交换完成？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

每个值应该移动到哪里，可以用一个公式表示：(i, j) 会移动到 (j, n-1-i)。难点在于不使用第二个矩阵来移动值，因为把值写入新单元格时，会覆盖尚未移动的值。先转置，再反转每一行，就能通过成对交换实现同样的四分之一圈旋转。

构建旋转副本

思路

第 i 行变成第 n-1-i 列，行中位置 j 的值会落在该列向下第 j 个位置，也就是第 j 行。因此，result[j][n-1-i] = matrix[i][j]。在第一个示例中，第 2 行第 0 列的 4 会移到第 0 行第 0 列，所以答案以 4 开头。

这些值会沿着长度为 4 的循环移动，因此原地写入会在值移动之前将其覆盖：3 会覆盖右上角的 1。复制需要额外占用 n² 个单元格，当 n = 70 时需要 4,900 个。

算法

创建一个 n × n 的结果矩阵。
对于每一行 i 和每一列 j，将 matrix[i][j] 复制到 result[j][n-1-i]。
返回结果。

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

转置后，再反转每一行

思路

转置会将 (i, j) 移到 (j, i)，反转一行会将列 c 移到列 n-1-c。两者结合后，会将 (i, j) 移到 (j, n-1-i)，正好是旋转后的目标位置。

这两种操作都会原地进行，因为它们都由一组配对交换组成。转置时，matrix[i][j] 和 matrix[j][i] 各自应该位于对方的单元格中，因此交换一次就能完成两者的位置调整。只交换满足 j > i 的配对，否则每对都会被换回原位。反转一行时，交换两端的元素，然后逐步向中间移动。

在第一个示例中，转置得到 [[3, 9, 4], [7, 5, 8], [1, 2, 6]]：此时每一行都包含原矩阵中的一列。反转每一行后，就得到了答案。

转置会进行 n(n-1)/2 次交换，反转操作会进行 n·⌊n/2⌋ 次交换，因此时间复杂度为 O(n²)，额外内存只需几个变量。R 版本会先将输入复制到一个 R 矩阵中，因此额外内存复杂度为 O(n²)。

算法

对于主对角线以上的每个单元格 (i, j)，其中 j > i，将它的值与单元格 (j, i) 的值交换。
对于每一行，交换首尾两个值，然后从两端向中间移动，直到它们相遇。
返回矩阵。

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

易错点和边界情况

使用从 0 开始的 j 进行转置。每对元素都会交换两次，结果相互抵消，因此最终结果只是行顺序反转，形成镜像。
先反转再转置。这个顺序会让矩阵逆时针旋转。用一个 2 × 2 的矩阵测试就能发现问题：[[1, 2], [3, 4]] 必须变成 [[3, 1], [4, 2]]。
将 matrix[j][n-1-i] = matrix[i][j] 写入同一个矩阵。目标单元格中仍保存着尚未移动的值，这个值会丢失。
使用 n-i 而不是 n-1-i。使用从 0 开始的索引时，最后一列的索引是 n-1，因此当 i = 0 时，n-i 会超出范围。

常见问题3

旋转矩阵的时间复杂度和空间复杂度是多少？

旋转一个 n × n 矩阵需要 O(n²) 时间，因为几乎每个值都需要移动一次。转置再反转的方法需要 O(1) 的额外空间。创建旋转后的副本同样需要 O(n²) 时间，但会使用 O(n²) 的额外空间。

如何将矩阵逆时针旋转？

交换这两个步骤的顺序：先反转每一行，再转置。你也可以先转置，再反转行的顺序。无论哪种方式，(i, j) 处的值最终都会到达 (n-1-j, i)。

你能一次移动四个值来旋转矩阵吗？

是的。中心之外的每个值都属于一个包含 4 个单元格的循环：(i, j)、(j, n-1-i)、(n-1-i, n-1-j) 和 (n-1-j, i)。按层处理时，将每个循环中的一个值暂存到变量中，再移动其他三个值。它的时间复杂度同样是 O(n²)，空间复杂度是 O(1)，不过需要处理更多索引运算，更容易出错。

def rotateImage(matrix):
    # 在这里编写代码

测试 #1

测试 #2

参数

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

预期输出

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