二维数组旋转的方法

目标：有一个N*N的二维数组，需要将将这个二维数组旋转90度。效果如下图思路一：生成一个新的二维数组，然后逐个元素填写数据。最后再覆盖掉原数组。根据上图，很容易得出坐标关系:通过逐位遍历，即可完成。#python3def unit_rotate_1(block_unit):list_len = len(block_unit)#复制一下二维数组tmp_unit = [[block_unit[j][i

xiaohuima_dong

8957人浏览 · 2021-04-08 17:02:05

xiaohuima_dong · 2021-04-08 17:02:05 发布

目标：有一个N*N的二维数组，需要将将这个二维数组旋转90度。效果如下图

思路一：

生成一个新的二维数组，然后逐个元素填写数据。最后再覆盖掉原数组。

根据上图，很容易得出坐标关系:

$Ba_{i,j} = Aa_{(N-j-1), i}$

通过逐位遍历，即可完成。

#python3
def unit_rotate_1(block_unit):
    list_len = len(block_unit)

    #复制一下二维数组
    tmp_unit = [[block_unit[j][i] for i in range(list_len)] for j in range(list_len)]

    #直接逐个坐标点替换数据
    for i in range(list_len):
        for j in range(list_len):
            block_unit[i][j] = tmp_unit[list_len - j - 1][i]

这个方法是最直观简单的，但是缺点是需要拷贝一次二维数组，同时算法复杂度为 $O(n^{2})$

思路二：

二维数组在旋转过程中，如下图分圈，数据替换发生在同一圈上。

如果N为偶数，就有N/2圈。如果N为基数，就一共有N/2 + 1圈，由于中心点不用替换，所以还是N/2圈

找到以第一圈为例，找到数据交换规律。

假如A点坐标是 $a_{0, j}$ , 则:B点坐标就是 $a_{j, N-1}$ , C点坐标就是 $a_{N-1, N-1-j}$ , D点坐标就是 $a_{N-1-j, 0}$

第一圈的数值替换：

#python3

def unit_rotate_2(block_unit):
    unit_len = len(block_unit)
    for i in range(1):
        line_len = unit_len - i*2
        for j in range(line_len-1):
            tmp = block_unit[0][j]
            block_unit[0][j] = block_unit[line_len-1-j][0]
            block_unit[line_len-1-j][0] = block_unit[line_len-1][line_len-1-j]
            block_unit[line_len-1][line_len-1-j] = block_unit[j][line_len-1]
            block_unit[j][line_len-1] = tmp

第二圈时，可以看成是坐标系i和j都偏移了1，同时边长N减少2，第m圈时偏移了m，边长n=N-m*2. 所以直接在上面柜代码中的坐标位置上加上偏移量即可。

#python3

def unit_rotate_2(block_unit):
    unit_len = len(block_unit)
    for i in range(int(unit_len/2)):
        line_len = unit_len - i*2
        for j in range(line_len-1):
            tmp = block_unit[0+i][j+i]
            block_unit[0+i][j+i] = block_unit[line_len-1-j+i][0+i]
            block_unit[line_len-1-j+i][0+i] = block_unit[line_len-1+i][line_len-1-j+i]
            block_unit[line_len-1+i][line_len-1-j+i] = block_unit[j+i][line_len-1+i]
            block_unit[j+i][line_len-1+i] = tmp

这种方法时间复杂度同样为 $O(n^{2})$ ，但是不用进行拷贝

思路三：

与思路二一样，也是分每一圈处理。不同的时直接推断出任意坐标点对应的要交换数据的其他三个点坐标。

假设A点坐标是(i，j), 先推算D的坐标。

D点的纵坐标与A点的横坐标有关联，关系是两者相等，即 A(i,?) ~~ D(?, i)。

D点的横坐标与A点的纵坐标有关联，关系是 A(?, j) ~~ D(N-j-1, ?)

所以D点坐标的之于A点就是 A(i,j) ~~ D(N-j-1, i)

同样的，C点坐标之于D点坐标与D点之于A点坐标的关系是相同的，B点之于C也是相同的。

所以，以同样的关系，带入替换

#python3

def unit_rotate_3(block_unit):
    n = len(block_unit)
    for i in range(int(n/2)):
        for j in range(i, n - i - 1):
            tmp = block_unit[i][j]
            block_unit[i][j] = block_unit[n-j-1][i]
            block_unit[n-j-1][i] = block_unit[n-i-1][n-j-1]
            block_unit[n-i-1][n-j-1] = block_unit[j][n-i-1]
            block_unit[j][n-i-1] = tmp

这个方法相比方法二比较好理解一些，通过两个点的横纵坐标关系，推出普遍关系，其他点之间直接套用。

测试代码：

array_size = 10;
    #生成一个二维数组
    list2 = [[0 for j in range(array_size)] for i in range(array_size)]
    for i in range(len(list2)):
        for j in range(len(list2[i])):
            list2[i][j] = i*len(list2) + j

    #旋转前输出一次
    for i in range(len(list2)):
        print(list2[i])
    print("------------")
    
    #旋转
    unit_rotate_1(list2)
    
    #旋转后输出一次
    for i in range(len(list2)):
        print(list2[i])

输出结果：