2022年 11月 7日

python 遍历矩阵_Python3算法之十：矩阵旋转

关注微信公众号“酸痛鱼”，获得更多最新最全的文章。

本文中所涉及的代码，在未特殊声明的情况下，都是基于Python3程序设计语言编写的。

建议您在PC浏览器中阅读本文，以获得更好的阅读体验。

0

问题描述

实现一个函数，该函数接收一个n×n二维矩阵matrix，将该矩阵顺时针旋转90度。要求直接对参数matrix进行修改，函数不返回任务东西。

例如：

  1. 给定 matrix =
  2. [
  3.     [1, 2],
  4.     [3, 4],
  5. ]
  6. 旋转后为matrix=
  7. [
  8.     [4, 1],
  9.     [3, 2],
  10. ]
  11.  
  12. 给定matrix=
  13. [
  14.     [1, 2, 3],
  15.     [4, 5, 6],
  16.     [7, 8, 9],
  17. ]
  18. 旋转后matrix=
  19. [
  20.     [7, 4, 1],
  21.     [8, 5, 2],
  22.     [9, 6, 3],
  23. ]

在力扣上可以找到相同的题目，叫《旋转图像》，其官方题解中，给出了本文中最后一种（第四种）解法的两种实现方式，感兴趣的读者可以去了解一下。

本文中讨论到坐标时，都是以Python语法为参照的，即坐标是从0开始算的。由于旋转操作涉及到移动每一个元素，所以本题目的所有解法的时间复杂度都是O(N^2)，也就是至少遍历一次matrix。

对于矩阵的一次置换操作，如果连续做两遍，矩阵又回到了原来的样子，我们称这个置换是可逆的；否则，我们称这个置换是不可逆的。

1

公式法

对矩阵进行顺时针90度旋转，相当于把每个坐标(r, c)的元素移动到(tr, tc)上，这两个坐标满足如下的转转换关系：

  1. tr = c
  2. tc = n- r - 1

需要注意的是，上面的转换操作是不可逆的，比如A→B, B→C，A和C是不同的元素。当我们把A移动到B的时候，B的值被改成了A的值。所以我们必须先记录B的值，再做B→C的操作。同样，做B→C时，必须先记录C的值。实际上，我们并没有办法动态记录这些信息，所以我们只能先拷贝一份matrix，然后借助这份拷贝来直接对matrix进行操作。所以，这种解法遍历了两次matrix，拷贝一次，转换一次；而空间复杂度则为O(N^2)。

  1. def rotate(matrix):
  2.     n = len(matrix)
  3.  
  4.     # 复制matrix
  5.     copy = [[matrix[r][c] for c in range(n)] for r in range(n)]
  6.  
  7.     # 转换公式:源坐标(r, c)，目标坐标(tr, tc)
  8.     # tr = c, tc = n-r-1
  9.     for r in range(n):
  10.         for c in range(n):
  11.             tr = c
  12.             tc = n - r - 1
  13.             matrix[tr][tc] = copy[r][c]

2

二次置换法

将矩阵顺时针旋转90度，可以通过二次置换得到：先将矩阵倒置，再将倒置后的矩阵的每一个行的元素顺序倒置。

8b2f127b20276da85f23158a38479227.png

因为这两种置换操作都是可逆的，所以通过这个方式，空间复杂为O(1)；而这种方式也是遍历两次matrix，遍历次数与第一种解法的一样。

  1. def rotate(matrix):
  2.     n = len(matrix)
  3.  
  4.     # 矩阵倒置，即(r,c)->(c,r)
  5.     for r in range(n):
  6.         for c in range(r, n):
  7.             matrix[r][c], matrix[c][r] = matrix[c][r], matrix[r][c]
  8.  
  9.     # 每一行倒转
  10.     for r in range(n):
  11.         # 以下两行相当于：matrix[r] = matrix[r][::-1]
  12.         # 本着不修改matrix内部结构的原则，用下面的方式
  13.         for c in range(n // 2):
  14.             matrix[r][c], matrix[r][n - 1 - c] = matrix[r][n - 1 - c], matrix[r][c]

3

边整体旋转法

对于行列数都为n的矩阵，它总共有ceil(n / 2)圈（ceil表示向上取整）。我们可以通过对每一圈的四条边进行顺时针旋转来实现总体的效果。在边旋转过程中，我们需要先临时记录其中一条边的值，以便在最后将其放到目标的位置。所以边旋转法的空间空间复杂度为O(N)，而且只对matrix遍历了一次。

ccd379e55c4d96b381be22b6652e2d85.png

每条边从起始位置旋转到目标位置的坐标转换公式，各位读者请自行推导，本文将不对此进行详细解说。

  1. def rotate(matrix):
  2.     n = len(matrix)
  3.     mi = n - 1 # 最大索引
  4.  
  5.     # 每一圈loop，对四条边单独旋转
  6.     for loop in range(n // 2):
  7.         # 每一圈边长
  8.         length = mi - 2 * loop
  9.  
  10.         # 将左边存储到临时变量left中
  11.         left_c = loop
  12.         left_r_start = loop
  13.         left = [matrix[left_r_start + i][left_c] for i in range(length)]
  14.  
  15.         # 将底边存到左边
  16.         bottom_c_start = loop
  17.         bottom_r = mi - loop
  18.         for i in range(length):
  19.             matrix[left_r_start + i][left_c] = matrix[bottom_r][bottom_c_start + i]
  20.  
  21.         # 将右边存到底边
  22.         right_c = mi - loop
  23.         right_r_start = mi - loop
  24.         for i in range(length):
  25.             matrix[bottom_r][bottom_c_start + i] = matrix[right_r_start - i][right_c]
  26.  
  27.         # 将上边存到右边
  28.         top_r = loop
  29.         top_c_start = mi - loop
  30.         for i in range(length):
  31.             matrix[right_r_start - i][right_c] = matrix[top_r][top_c_start - i]
  32.  
  33.         # 将左边，即left存到上边
  34.         for i in range(length):
  35.             matrix[top_r][top_c_start - i] = left[i]

4

边元素依次旋转法

事实上，我们可以对每一圈的每条边上的每个元素单独进行旋转，这样的话，我们只需要临时记录其中的一个元素，以达到空间复杂度为O(1)的实现。

边元素旋转过程如图所示：

9121e5a83625dee2d4c1c5a944dda120.png 
def

e7d9df7f31ec65233e4b2923018ab807.png
微信扫码关注我哦