给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 python3

<think>好，我现在要解决的是如何原地旋转一个n×n的矩阵90度顺时针。这个问题要求不能使用额外的矩阵来存储结果，必须直接修改原矩阵。那么，我应该怎么做呢？ 首先，我得想清楚顺时针旋转90度的规律。假设有一个矩阵，比如3×3的： 1 2 3 4 5 6 7 8 9 旋转后应该是： 7 4 1 8 5 2 9 6 3 观察一下原来的元素位置如何变化。比如，原来的第一行变成最后一列，第二行变成中间列，第三行变成第一列。更一般地说，对于元素matrix[i][j]，旋转后的位置应该是哪里呢？可能变成[j][n-1-i]？或者有没有更明确的规律？ 或者，有没有可能通过多次翻转来实现旋转？比如，先转置矩阵，再翻转每一行。例如，原矩阵转置后得到： 1 4 7 2 5 8 3 6 9 然后翻转每一行，得到： 7 4 1 8 5 2 9 6 3 这正好是顺时针旋转90度的结果。那这种方法是否可行？这需要两次操作：转置和水平翻转。而且这两个操作都可以原地进行，不需要额外空间。这可能是一个可行的方法。 那具体步骤是： 1. 转置矩阵：交换matrix[i][j]和matrix[j][i]，其中i < j。这样可以避免重复交换。例如，对于i从0到n-1，j从i到n-1，交换这两个位置的元素。这样就能得到转置后的矩阵。 2. 然后每一行进行反转。比如，第一行原本是1 4 7，反转后变成7 4 1。其他行同理。这样整个矩阵就旋转了90度顺时针。 这样处理的话，时间复杂度是O(n²)，因为转置需要遍历大约n²/2次交换，反转每一行也需要O(n²)时间。空间复杂度是O(1)，因为没有使用额外空间，原地操作。 那如何实现这两个步骤呢？ 首先，转置矩阵。对于每个i，j，其中i < j，交换matrix[i][j]和matrix[j][i]。比如，在Python中，可以使用嵌套循环： for i in range(n): for j in range(i, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] 但是需要注意，这里当i和j相等时，交换其实不会改变，但为了代码简洁，可以保留。然后，对于每一行，进行反转。可以用列表的reverse方法，或者自己交换元素。 比如，对于每一行matrix[i]，执行matrix[i].reverse()。或者在代码中，对于每一行，交换第j个和第n-1-j个元素，直到中间位置。 但如果是二维数组，每一行是一个列表的话，直接调用reverse方法更方便。 所以整体的步骤就是： 转置矩阵 → 每一行反转。 那现在验证这个方法的正确性。比如，原来的例子： 转置后的矩阵： 1 4 7 2 5 8 3 6 9 然后每行反转： 第一行反转后是7 4 1 → 正确。 第二行是8 5 2 → 正确。 第三行是9 6 3 → 正确。整个结果正确。 另一个测试案例，比如2×2矩阵： 原矩阵： 1 2 3 4 转置后： 1 3 2 4 然后每行反转： 3 1 → 第一行 4 2 → 第二行？这似乎不对。或者，原矩阵旋转90度后的正确结果应该是： 3 1 4 2 → 因为原矩阵顺时针旋转后应该是： 3 1 4 2。是的，转置后的矩阵是： 1 3 2 4 → 每行反转得到3 1和4 2，正确。 所以方法正确。 那这样，Python代码的大致步骤是： n = len(matrix) 转置矩阵 → 交换i,j和j,i，其中i < j。 然后，每一行反转。 那这样代码怎么写？ 例如： def rotate(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 row in matrix: row.reverse() 这样应该就可以实现原地旋转。但是需要确认是否在Python中这样的操作是原地的。是的，因为列表的reverse方法是原地操作的，交换元素也是原地的。 那这样就能满足题目的要求了。不需要额外空间，直接修改原矩阵。 有没有其他方法？比如，直接旋转四个对应元素的位置。比如，对于每个环，每次旋转四个元素的位置。例如，对于最外层的环，每个元素的位置转换四次，每次交换四个位置的值。这种方法可能更高效一些，但实现起来稍微复杂。 例如，对于一个n×n的矩阵，我们可以分层处理。对于每一层，将其分为四个部分，每次交换四个元素的位置。例如，对于位置(i,j)，旋转后的位置是(j, n-1-i)。但是这样的话，可能需要逐个元素的处理，并且需要注意循环的次数，避免重复处理。 比如，对于每一层，从第i层到n-1-i层，处理该层中的元素。例如，对于n=4，处理最外层i=0到i=3。每一层需要处理n-1-2i次元素？或者具体的循环次数需要计算。 比如，对于n=3，层数是1层（中间元素不需要处理）。对于该层，四个角的元素需要交换。例如，假设i是当前层的起始索引。那么对于i=0，处理到n-1 -i=2。那么对于j从i到 n-1 -i -1。例如，当i=0，j的范围是0到1（因为n=3，n-1-i=2，所以j从0到2-1=1）。 对于每个j，交换四个元素的位置： temp = matrix[i][j] matrix[i][j] = matrix[n-1-j][i] matrix[n-1-j][i] = matrix[n-1-i][n-1-j] matrix[n-1-i][n-1-j] = matrix[j][n-1-i] matrix[j][n-1-i] = temp 这可能有点复杂，但这样可以原地交换四个元素的位置。这种方法的时间复杂度同样是O(n²)，但可能更直接一些。 例如，假设i是层数，从0到n//2 -1。对于每个i，处理j从i到n-1 -i -1。每个这样的j对应四个元素的位置。 比如，对于n=3，i=0，j的范围是0到0（因为n-1 -i -1=3-1-0-1=1-0-1=0？可能我的计算有问题，需要再仔细分析）。 或者，更明确的例子： 对于i是层数，从0到n//2 -1。对于每个i，j的范围是i到n-2 -i。比如，当n=4时，i=0时j从0到1，处理四个元素。例如，当i=0，j=0时，交换四个元素的位置： (0,0) → (0,3) (0,3) → (3,3) (3,3) → (3,0) (3,0) → (0,0) 可能这样，需要交换这四个位置的元素。但具体的转换可能需要更仔细的坐标计算。 这个方法虽然可能更高效，但代码实现较为复杂。而转置加反转的方法更简单，容易理解和实现。 那么，在实际编程中，可能转置加反转的方法更为简便。因此，这可能是一个更优的解决方案。特别是对于Python来说，代码会更简洁。 所以，最终的解决方案是：转置矩阵，然后反转每一行。 这样，代码的编写就变得简单了，而且正确性已经验证过了。 总结一下步骤： 1. 转置矩阵：交换元素matrix[i][j]和matrix[j][i]，其中i < j。这可以通过双重循环实现，外层循环i从0到n-1，内层循环j从i到n-1。 2. 反转每一行的元素：对每一行，使用reverse方法或者手动交换元素，将行反转。 这样，矩阵就被顺时针旋转了90度，原地修改，无需额外空间。 现在测试一下这个方法是否正确。比如，对于另一个例子，n=2： 原矩阵： 1 2 3 4 转置后： 1 3 2 4 然后反转每一行： 3 1 → 第一行 4 2 → 第二行。正确。 另一个测试用例，n=4： 原矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 转置后的矩阵： 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 然后反转每一行： 13 9 5 1 → 第一行 14 10 6 2 → 第二行 15 11 7 3 → 第三行 16 12 8 4 → 第四行 而顺时针旋转90度的正确结果应该是： 13 9 5 1 14 10 6 2 15 11 7 3 16 12 8 4 → 对吗？ 原矩阵顺时针旋转90度后的正确结果应该是： 原矩阵的第一列13,14,15,16变成第一行的逆序，即13,9,5,1？ 或者可能我哪里搞错了。或者应该直接看原矩阵旋转后的结果。比如： 原矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 顺时针旋转90度后，每个元素的位置变化为： 原来的行i变成列n-1 -i。例如，原行0的1 2 3 4变成新矩阵的第3列的4 3 2 1？或者可能我的理解有误。 或者，我应该将原矩阵顺时针旋转90度后的每个元素的位置转换规律是：原matrix[i][j] → 新matrix[j][n-1-i]。或者原matrix[i][j]会被移动到新matrix[j][n-1 -i]的位置？ 例如，原矩阵中的元素1在位置（0,0）。旋转后应该在（0,3）吗？或者原矩阵中的元素1会被移动到哪？ 顺时针旋转90度的话，原来的行0，列0的元素应该移动到行0，列3的位置吗？比如，对于n=4： 原矩阵的每个元素matrix[i][j]在旋转后的位置应该是matrix[j][n-1 -i]吗？ 例如，原矩阵中的元素1（0,0）→ 旋转后到（0,3）？原行0的元素变成列3，但顺序反转吗？ 或者，另一种方式：例如，原矩阵顺时针旋转90度，相当于将行i变为列n-1 -i，并且顺序反转。例如，原行0的元素变成列3，并且顺序倒置。 所以，原行0的1,2,3,4在旋转后变为列3的4,3,2,1。所以新矩阵的第一行是13,9,5,1 → 这似乎不正确。或者可能我应该更仔细地分析。 原矩阵顺时针旋转90度后的正确结果应该是： 原矩阵的最后一列（4,8,12,16）变成第一行，顺序是16,12,8,4 → 而原倒数第二列（3,7,11,15）变成第二行，顺序是15,11,7,3 → 以此类推。 或者，可能我之前的转置加反转的方法得到的结果是否正确？ 例如，原矩阵转置后的矩阵是： 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 16 然后反转每一行得到： 13 9 5 1 → 行0 14 10 6 2 → 行1 15 11 7 3 → 行2 16 12 8 4 → 行3 这应该就是顺时针旋转后的矩阵。因为原来的转置操作相当于沿主对角线翻转，此时每一行反转，相当于将行逆序，相当于将整个矩阵顺时针旋转90度。那是否正确？ 比如，原来的每个元素matrix[i][j]在转置后是matrix[j][i]，然后反转行，得到matrix[j][n-1 -i]。这正是顺时针旋转90度的坐标变换。例如，原来的位置i,j经过转置后变成j,i，然后行反转，变成j, n-1 -i。所以，总的变换是matrix[i][j] → matrix[j][n-1 -i]，这确实是顺时针旋转90度的结果。 所以，方法正确。 那这个方法是可行的。代码实现起来也很简单，所以在Python中按照这个步骤实现即可。</think>要将一个 $n \times n$ 的二维矩阵**原地**顺时针旋转 90 度，可以通过以下两步实现： ### 方法分析 1. **转置矩阵**：将矩阵的行和列交换，即 $matrix[i][j] \leftrightarrow matrix[j][i]$。 2. **反转每一行**：将转置后的每一行元素逆序排列。 ### 数学推导 - **转置**：将矩阵沿主对角线翻转，元素位置变为 $matrix[j][i]$。 - **反转行**：将每行的顺序从 $[a_0, a_1, ..., a_{n-1}]$ 变为 $[a_{n-1}, ..., a_1, a_0]$。 组合这两步后，原矩阵的顺时针旋转等效于： 原元素 $matrix[i][j]$ → 转置后为 $matrix[j][i]$ → 反转行后为 $matrix[j][n-1-i]$，即顺时针旋转 90 度的位置。 --- ### Python 实现 ```python def rotate(matrix): n = len(matrix) # 转置矩阵 for i in range(n): for j in range(i, n): # 避免重复交换，j从i开始 matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 反转每一行 for row in matrix: row.reverse() ``` ### 示例验证 以矩阵 $\begin{bmatrix}1&2&3\\4&5&6\\7&8&9\end{bmatrix}$ 为例： 1. **转置**后： $$ \begin{bmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{bmatrix} $$ 2. **反转每一行**后： $$ \begin{bmatrix} 7 & 4 & 1 \\ 8 & 5 & 2 \\ 9 & 6 & 3 \end{bmatrix} $$ 结果正确。 --- ### 复杂度 - **时间复杂度**：$O(n^2)$，需要遍历矩阵两次。 - **空间复杂度**：$O(1)$，原地操作，无额外空间使用。 此方法简洁高效，直接修改原矩阵，满足题目要求。