LeetCode 面试题 01.07. 旋转矩阵
题目描述
题意分析
将
n × n方阵顺时针旋转九十度，直接修改输入矩阵，并使用常数额外空间。原位置(row, col)的元素应移动到(col, n - 1 - row)，不能仅创建一个旋转后的新矩阵返回。
解法：先转置再反转每一行
核心思路
[!blue]
顺时针旋转后，原来的第
row行变成从右往左数的第row列，因此新列号为n - 1 - row；原来从左往右递增的列号变成从上往下递增的行号，因此新行号为col。这就得到目标映射(row, col) → (col, n - 1 - row)。把这个映射拆成两个可以原地完成的操作：先沿主对角线转置，让
(row, col)变成(col, row)；再反转每一行，把当前列号row变成n - 1 - row，当前行号col保持不变。两步合起来恰好就是顺时针旋转。转置时，
matrix[row][col]与matrix[col][row]是同一对位置。只遍历严格上三角col > row，就能让每一对恰好交换一次；遍历整个矩阵会在下三角再次把它们交换回来。主对角线上的元素在这一步无需交换。反转一行时，让双指针从首尾向中间移动，每次交换一对左右对称位置。指针外的元素已经到达反转后的目标列，只需继续处理内部；当指针相遇或交错时，该行处理完成。奇数长度中间的元素本就不需要交换。
两个阶段都只交换原矩阵中的元素，临时变量保存被覆盖的值，因此不会丢失数据，也无需新矩阵。
n = 1时两个阶段都不发生交换，结果自然保持不变。
解题步骤
- 记录矩阵边长
n，遍历每一行row。- 从
col = row + 1开始遍历这一行的上三角部分，交换matrix[row][col]与matrix[col][row]，完成转置。- 对每一行令
left = 0、right = n - 1，在left < right时交换两端元素，再同时向中间移动。- 所有行反转结束后，输入矩阵已经成为目标结果，无需返回新矩阵。
代码实现
class Solution {
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int row = 0; row < n; row++) {
// 只交换主对角线一侧，避免同一对元素交换两次。
for (int col = row + 1; col < n; col++) {
int value = matrix[row][col];
matrix[row][col] = matrix[col][row];
matrix[col][row] = value;
}
}
// 转置后再逐行反转，两次映射合成为顺时针九十度。
for (int[] row : matrix) {
for (int left = 0, right = n - 1; left < right; left++, right--) {
int value = row[left];
row[left] = row[right];
row[right] = value;
}
}
}
}
func rotate(matrix [][]int) {
n := len(matrix)
for row := 0; row < n; row++ {
// 只交换主对角线一侧，避免同一对元素交换两次。
for col := row + 1; col < n; col++ {
matrix[row][col], matrix[col][row] = matrix[col][row], matrix[row][col]
}
}
for row := 0; row < n; row++ {
// 转置后再逐行反转，两次映射合成为顺时针九十度。
for left, right := 0, n-1; left < right; left, right = left+1, right-1 {
matrix[row][left], matrix[row][right] = matrix[row][right], matrix[row][left]
}
}
}
复杂度分析
- 时间复杂度：$O(n^2)$。转置交换 $n(n-1)/2$ 对位置，逐行反转共进行 $n\lfloor n/2 \rfloor$ 次交换。
- 空间复杂度：$O(1)$。只用下标和交换所需的临时变量，所有元素仍存放在原矩阵中。
关键点总结
[!green]
- 先根据旋转方向写出坐标映射，再拆成转置与行反转。
- 上三角遍历保证转置中的每一对位置只交换一次。
- 原地交换保留所有原值，两个阶段的坐标变换共同得到最终位置。
易错点总结
[!yellow]
- 转置后必须反转每一行；若改为反转每一列，得到的是逆时针旋转。
- 主对角线只在转置阶段不动，不能因此跳过这些元素的行反转。
- 直接把元素写入最终坐标，会覆盖还未读取的原值；交换时必须先保存原值，或使用 Go 的多重赋值。
- 行反转的右指针从
n - 1开始，循环条件是left < right，避免越界或重复交换。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 867. 转置矩阵 | 简单 | 顺时针旋转可拆成矩阵转置再逐行反转，原题只做转置。 |
| 344. 反转字符串 | 简单 | 矩阵转置后逐行反转，每一行的处理都可直接复用左右双指针交换算法。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！