数组应用【旋转数组】
程序员文章站
2022-04-16 16:00:34
题目:You are given an nx n2D matrix representing an image.Rotate the image by 90 degrees (clockwise).Follow up:Could you do this in-place分析: 给一个N*N的数组,旋转90度,不可以开辟额外空间 已N=3进行分析: 旋转后变为 ①我们把焦点放在一个元素的旋转上,可以看出要在员数组中旋转,在不丢失数据......
题目:
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place
分析:
给一个N*N的数组,旋转90度,不可以开辟额外空间
已N=3进行分析:
旋转后变为
①我们把焦点放在一个元素的旋转上,可以看出要在员数组中旋转,在不丢失数据的情况下,每个值的要旋转会“波及”4个数,以1为例波及到了1,3,7,9,每个数旋转要不丢失数据就要考虑如何让这个4个数都得以保留。
在这里我们引入一个临时变量,数交换的问题就解决了。
top=matrix[first][i] #save top
#left->top
matrix[first][i]=matrix[last-offset][first];
#bottom->left
matrix[last-offset][first]=matrix[last][last-offset];
#right->botton
matrix[last][last-offset]=matrix[i][last];
#top->right
matrix[i][last]=top;
②现在还有一个问题就是如何才能完整的把所有的数都旋转90度且不会多旋:在这里我们可以把每条边看成一个整体
通过发现旋转次数:N/2
'''
layer 旋转层数
'''
def rotate_in_place(matrix):
n=len(matrix)
for layer in range(n//2):
first=layer
last=n-layer-1
for i in range(first,last):
offset =i-first #偏移量
top=matrix[first][i] #save top
#left->top
matrix[first][i]=matrix[last-offset][first];
#bottom->left
matrix[last-offset][first]=matrix[last][last-offset];
#right->botton
matrix[last][last-offset]=matrix[i][last];
#top->right
matrix[i][last]=top;
for x in matrix:
print(x, sep=" ")
matrix=[
[0,1,2,3,4],
[5,6,7,8,9],
[10,11,12,13,14],
[15,16,17,18,19],
[20,21,22,23,24]
]
rotate_in_place(matrix)
本文地址:https://blog.csdn.net/m0_37806112/article/details/107448110
上一篇: 编写一个基本计算器
下一篇: python中字典的增删改查