欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

数组应用【旋转数组】

程序员文章站 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

相关标签: 内功