给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。 你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。 示例 1： 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

<think>嗯，我现在要解决的是如何将一个n×n的矩阵顺时针旋转90度，而且必须原地修改，不能使用额外的矩阵。这个问题看起来有点挑战性，我需要仔细思考一下。 首先，我得想清楚旋转后的位置变化规律。比如，示例中的输入是一个3×3的矩阵，旋转之后，原来的第一行变成了倒数第一列，第二行变成倒数第二列，依此类推。比如原来的元素1的位置是(0,0)，旋转后到了(0,2)的位置；元素2(0,1)到了(1,2)；元素3(0,2)到了(2,2)。那是不是每个元素的位置变化有什么规律呢？ 假设原矩阵中的某个元素的位置是(i,j)，顺时针旋转90度之后，它的位置应该变为(j, n-1 -i)。比如在3×3的情况下，i=0，j=0，变成(0,2)。那是不是这样？或者可能我的这个推导有问题？ 或者另一个思路，旋转90度可以通过先转置矩阵，然后反转每一行来实现。比如原矩阵转置之后，行和列交换，然后每一行反转，就能得到顺时针旋转90度的结果。例如，原矩阵转置后的行变成列，比如原来的行[1,2,3]转置后变成第一列[1,4,7]。然后反转每一行，比如第一列变成行，反转后是7,4,1。这样整个矩阵就被正确旋转了。那这样的话，这个方法的步骤应该是：先转置矩阵，再反转每一行。这样的话，是否可以原地操作？ 那转置矩阵的话，怎么原地转置呢？比如对于n×n的矩阵，转置就是交换i,j和j,i的元素。但要注意，只需要遍历上三角或者下三角，否则会交换两次导致恢复原样。例如，对于每个i从0到n-1，j从i到n-1，交换matrix[i][j]和matrix[j][i]。这样就能完成原地转置。然后再将每一行进行反转。例如，第一行从左到右反转，这样每个行的元素顺序就被调换了。 比如示例中的矩阵： 原矩阵： 1 2 3 4 5 6 7 8 9 转置后变成： 1 4 7 2 5 8 3 6 9 然后每一行反转，得到： 7 4 1 8 5 2 9 6 3 这正是正确的输出。所以这个方法是可行的。那这样的方法的时间复杂度是O(n²)，空间复杂度是O(1)，因为原地操作。 那这样的话，实现起来应该分两步： 1. 转置矩阵：遍历矩阵的上三角部分，交换matrix[i][j]和matrix[j][i]。 2. 反转每一行的元素：对每一行，使用双指针方法，交换首尾对应的元素直到中间。 那这样具体怎么实现呢？比如对于一个n×n的矩阵： 转置部分，i从0到n-1，j从i到n-1。例如，当i=0时，j从0到n-1，但实际上转置只需要交换i<j的情况。或者，如果i和j的范围是i从0到n-1，j从i+1到n-1的话，这样每个元素只交换一次？或者可能我之前描述的范围是错的？ 比如，正确的转置应该是对于每个i < j的元素，交换matrix[i][j]和matrix[j][i]。例如，当i=0，j=1时交换（0,1）和（1,0）；当i=0，j=2时交换（0,2）和（2,0）等等。所以转置的正确循环应该是i从0到n-1，j从i+1到n-1。这样就能避免重复交换。例如，对于3×3矩阵： 原来的元素（0,1）和（1,0）交换一次，之后就不会再处理到（1,0）的情况，因为i的范围是i到n-1，而j是i+1开始。所以这样可以正确完成转置。 然后反转每一行的部分，对于每一行row，反转的操作是将row[left]和row[right]交换，然后left加一，right减一，直到left >= right。 那这样的话，代码的大致结构应该是： for i in 0..n-1: for j in i+1..n-1: swap(matrix[i][j], matrix[j][i]) for each row in matrix: reverse the row. 这样就能得到顺时针旋转90度的结果。 那有没有其他方法呢？比如直接通过四次交换的方式，每次旋转四个对应位置的元素。这种方法可能更直接，但需要找出每个元素旋转后的位置，然后进行交换。 比如，对于每个元素的位置(i,j)，旋转后的位置是(j, n-1 -i)。然后这四个位置的元素可以按顺序交换。例如，假设四个位置分别是A,B,C,D，每次交换这四个的位置，这样就能完成原地旋转。这种方法需要确定哪些元素需要被处理，以避免重复交换。 例如，在n为偶数的时候，比如4×4的矩阵，可以将矩阵分成四个象限，每个象限处理对应的四个元素。而对于n为奇数的时候，中间的元素不需要旋转，其他元素同样处理。 这种情况下，每一轮处理四个元素。这样的方法的时间复杂度同样是O(n²)，但可能需要更复杂的索引操作。 比如，对于每个层（layer）来说，从外层到内层处理。例如，对于n=3，处理最外层，四个边上的元素。每一层需要处理四个元素为一组的旋转。例如，对于元素(i,j)来说，属于某个环的位置，旋转四个的位置。例如，在n=3的情况下，最外层需要处理四个角的元素，以及边中间的四个元素？ 或者，可能更简单的方法是分层处理。例如，对于每个环（layer），从外到内。每层有边长len，比如len = n - 2*layer。然后对于每层的每个元素，进行四次交换。 比如，考虑一个n×n的矩阵，其中layer的范围是0到(n//2 -1)。对于每个layer，处理该层上的所有元素。比如，在layer=0时，处理最外层的环；layer=1时处理次外层，直到中间的最后一个环。 对于每个layer，我们需要遍历该层上的元素。例如，在layer层中，行的范围是layer到n-1 - layer。比如，对于每个元素在该层上的第一个边（上边），从i=layer，j从layer到n-1 - layer -1。然后，这四个边的元素需要被旋转。 或者，更具体地说，对于每个layer，我们需要处理该层上的每个元素，除了最后一个，因为每个元素会被四次交换覆盖。例如，对于一个n=4的layer=0的情况，边长是4-2*0=4，但实际需要处理的元素数量是边长-1，即3。即每个边处理三个元素，然后这四个边的元素会被旋转。 比如，假设当前处理的位置是i和j。那么对于顺时针旋转，四个对应的位置是： 原位置：(i,j) 顺时针90度后的新位置：(j, n-1 -i) 然后继续旋转这个新位置，得到下一个位置：(n-1 -i, n-1 -j) 再旋转得到：(n-1 -j, i) 然后再次旋转回到原位置的某个位置？或者可能需要四次交换才能完成这四个位置的循环。 例如，四个位置分别是： pos1 = (i, j) pos2 = (j, n-1 -i) pos3 = (n-1 -i, n-1 -j) pos4 = (n-1 -j, i) 这四个位置的元素需要依次交换。比如，将pos1的值存到temp，然后将pos4的值放到pos1，pos3的值放到pos4，pos2的值放到pos3，temp的值放到pos2。或者类似这样的顺序，完成四个位置的交换。 因此，对于每个元素，我们只需要处理一次，然后这四个位置的元素都会被正确旋转。 这种情况下，应该如何遍历这些元素？ 比如，在layer层，i的范围是layer到n-layer-1 -1。例如，假设n=4，layer=0，那么i的范围是0到3-1=2？或者可能需要更仔细的边界条件。 可能更准确的做法是，对于每个layer，处理从i=layer到i < n-layer-1的元素。例如，对于每个i，j的范围是layer到n-layer-1 -1。例如，当n=3，layer=0时，j的范围是0到1。这样，每个元素会被处理一次，而不会重复。 这种情况下，每个元素对应的四个位置会被正确交换四次，从而达到旋转的目的。 举个例子，假设matrix是4×4的： 初始的四个角元素是(0,0), (0,3), (3,3), (3,0)。这四个元素需要交换。然后，处理(0,1)的时候，对应的四个位置是(1,3), (3,2), (2,0)，等等。 这个时候，可能需要这样的循环结构： for layer in 0...n//2-1: for i in layer...n-layer-2: temp = matrix[layer][i] # 找到四个位置并交换 # pos1是(layer, i) # pos2是(i, n-1 - layer) # pos3是(n-1 - layer, n-1 - i) # pos4是(n-1 - i, layer) # 交换这四个位置的元素 # 比如，保存pos1的值到temp，然后将pos4的值给pos1，pos3给pos4，pos2给pos3，temp给pos2 # 或者使用四次交换操作 假设具体操作是这样的： 对于每个layer，循环i从0到n-2*layer-1 -1。或者可能i的范围需要根据layer进行调整。比如，在每层中，我们需要处理该层的每个元素，除了最后一个，因为每个元素会被四次交换覆盖。 例如，当处理最外层layer=0时，边长是n。此时，该层的每边需要处理n-1个元素。例如，n=4时，处理3个元素，每个边处理三个元素。那么，循环变量i从0到n-1-layer*2-1。例如，当layer=0，i从0到3-1=2？这样，每个元素被处理一次，而不会重复。 这可能比较复杂，需要仔细计算索引。但是，这种方法的好处是可以在原地交换，无需转置和反转，但实现起来可能更繁琐。 回到用户的问题，他要求必须原地旋转，所以两种方法都是可行的。第一种方法（转置后反转行）可能更容易实现，代码更简洁，而第二种方法可能更高效，但需要处理更多边界条件。 那么，具体如何选择呢？比如，对于编程面试来说，第一种方法可能更简单，容易记住，而第二种方法可能考察对旋转过程的深入理解。 那现在，我需要确认第一种方法是否正确。比如，转置矩阵后，再反转每一行，是否等价于顺时针旋转90度？ 举个例子，假设原矩阵是： 1 2 3 4 5 6 7 8 9 转置后的矩阵是： 1 4 7 2 5 8 3 6 9 然后反转每一行，得到： 7 4 1 8 5 2 9 6 3 这确实是正确的顺时针旋转90度的结果。 另一个例子，假设原矩阵是： 5 1 9 11 2 4 8 10 13 3 6 7 15 14 12 16 转置之后是： 5 2 13 15 1 4 3 14 9 8 6 12 11 10 7 16 反转每一行得到： 15 13 2 5 14 3 4 1 12 6 8 9 16 7 10 11 而正确的顺时针旋转90度后的结果应该是： 15 13 2 5 14 3 4 1 12 6 8 9 16 7 10 11 所以这似乎是对的。那这说明第一种方法是正确的。 所以，这种方法确实可行。那对于代码实现来说，这可能是更简单的方式。那用户的问题要求必须原地修改，而这种方法是否满足原地？ 是的，因为转置和反转行都是原地操作，不需要额外的矩阵。 那现在，如何编写这个过程的代码？ 假设使用Python的话： def rotate(matrix): n = len(matrix) # 转置矩阵 for i in range(n): for j in range(i+1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 反转每一行 for row in matrix: row.reverse() 那这个代码是否正确呢？比如，对于示例中的情况，确实正确。那这应该是正确的解决方案。 那这就是一个可行的解决方案。但是，用户的问题是否允许这种方法？因为题目中说“请不要使用另一个矩阵来旋转图像”，而这里没有使用额外的矩阵，只是交换元素，所以满足条件。 那这个方法的时间复杂度是O(n²)，因为转置需要O(n²/2)次交换，反转每一行需要O(n²/2)次交换。总的操作次数是O(n²)，和矩阵大小成正比。 那这可能就是最优的解决方案。 那现在，我需要将这个过程详细地解释出来，帮助用户理解。 总结步骤： 1. 转置矩阵：将矩阵的行变成列，即交换matrix[i][j]和matrix[j][i]，其中i < j，以避免重复交换。 2. 反转每一行：将每一行的元素顺序反转，即第一个元素和最后一个交换，第二个和倒数第二个交换，依此类推。 这样，矩阵就被顺时针旋转了90度。 例如，转置操作将矩阵的行和列互换，这样原来的行变成了列。但此时矩阵并没有完全达到顺时针旋转的效果。例如，转置后的第一列是原矩阵的第一行，但顺时针旋转后的第一列应该是原矩阵的最后一行。因此，转置之后反转每一行的元素顺序，就能得到正确的旋转结果。 那这样的方法是不是总正确呢？比如，不管矩阵的大小是奇数还是偶数，都是正确的？ 是的。因为转置和反转行的操作不受矩阵奇偶性的影响。 那这可能就是正确的解决方案。那用户需要按照这种方法来编写代码，满足原地修改的条件。</think>要将一个 $n \times n$ 的矩阵原地顺时针旋转 90 度，可以通过以下两步实现： ### 方法思路 1. **转置矩阵**：将矩阵的行和列互换，即 $matrix[i][j]$ 与 $matrix[j][i]$ 交换。 2. **反转每一行**：将每一行的元素顺序反转。 通过这两步操作，即可在不使用额外空间的情况下完成顺时针旋转。 --- ### 步骤说明 1. **转置矩阵**： - 遍历矩阵的上三角部分（即 $i < j$ 的情况），交换元素 $matrix[i][j]$ 和 $matrix[j][i]$。 - 例如，原始矩阵： $$ \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{bmatrix} $$ 转置后变为： $$ \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} $$ --- ### 代码实现 ```python def rotate(matrix): n = len(matrix) # 转置矩阵 for i in range(n): for j in range(i + 1, n): matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] # 反转每一行 for row in matrix: row.reverse() ``` --- ### 复杂度分析 - **时间复杂度**：$O(n^2)$。转置和反转每一行各需要 $O(n^2/2)$ 次操作，总体为 $O(n^2)$。 - **空间复杂度**：$O(1)$。完全原地操作，未使用额外空间。 --- ### 示例验证 以输入 `matrix = [[1,2,3],[4,5,6],[7,8,9]]` 为例： 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} $$ 结果与预期一致，验证了方法的正确性。