矩阵旋转

发表于 更新于 分类于 阅读次数： 本文字数： 540 阅读时长 ≈ 2 分钟

给你一幅由 N × N 矩阵表示的图像，其中每个像素的大小为 4 字节。请你设计一种算法，将图像旋转 90 度。

不占用额外内存空间能否做到？

示例 1:

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

原地旋转输入矩阵，使其变为: [ [7,4,1], [8,5,2], [9,6,3]] 示例 2:

给定 matrix = [ [ 5, 1, 9,11], [ 2, 4, 8,10], [13, 3, 6, 7], [15,14,12,16]],

原地旋转输入矩阵，使其变为: [ [15,13, 2, 5], [14, 3, 4, 1], [12, 6, 8, 9], [16, 7,10,11]]

官方给出了三种解法:

  1. 使用辅助数组
  2. 原地旋转
  3. 翻转代替旋转:
    • ① 沿主对角线翻转，然后再沿垂直中心轴翻转；轴示意图： |
    • ② 沿水平轴翻转，再沿主对角线翻转（力扣解法三）；轴示意图：—
    • ② 沿副对角线（左下到右上）翻转，再水平轴翻转（ gpt 解法）；轴示意图：/ —
    • ④ 沿垂直中心轴翻转，再沿副对角线翻转。轴示意图：| /

第 ② 种解法代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * @param {number[][]} matrix
 * @return {void} Do not return anything, modify matrix in-place instead.
 */
var rotate = function (matrix) {
  const n = matrix.length;

  // Step 1: 沿着副对角线交换元素
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n - i; j++) {
      // 交换 matrix[i][j] 和 matrix[n-j-1][n-i-1]
      [matrix[i][j], matrix[n - j - 1][n - i - 1]] = [
        matrix[n - j - 1][n - i - 1],
        matrix[i][j],
      ];
    }
  }

  console.log(matrix); // 可以先注释下面循环看打印信息，输出 [[9, 6, 3], [8, 5, 2], [7, 4, 1]]

  // Step 2: 沿着中心水平线翻转
  for (let i = 0; i < Math.floor(n / 2); i++) {
    for (let j = 0; j < n; j++) {
      // 交换 matrix[i][j] 和 matrix[n-i-1][j]
      [matrix[i][j], matrix[n - i - 1][j]] = [
        matrix[n - i - 1][j],
        matrix[i][j],
      ];
    }
  }
};

const matrix1 = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9],
];
rotate(matrix1);
console.log(matrix1); // 输出 [[7, 4, 1], [8, 5, 2], [9, 6, 3]]

复杂度分析

时间复杂度：O(N²)，其中 N 是 matrix 的边长。对于每一次翻转操作，我们都需要枚举矩阵中一半的元素。

空间复杂度：O(1)。为原地翻转得到的原地旋转。

TIPS:

不要被程序中各种下标唬住，可以带入实际的数字，一步步分析，调试看打印信息。