Programa Python3 para rotar en su lugar la array cuadrada 90 grados | Serie 1

Dada una array cuadrada, gírela 90 grados en sentido contrario a las agujas del reloj sin usar ningún espacio adicional.
Ejemplos: 
 

Input:
Matrix:
 1  2  3
 4  5  6
 7  8  9
Output:
 3  6  9 
 2  5  8 
 1  4  7 
The given matrix is rotated by 90 degree 
in anti-clockwise direction.

Input:
 1  2  3  4 
 5  6  7  8 
 9 10 11 12 
13 14 15 16 
Output:
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13
The given matrix is rotated by 90 degree 
in anti-clockwise direction.

Aquí ya se analiza un enfoque que requiere espacio adicional .
Planteamiento: Para resolver la pregunta sin ningún espacio adicional, gire la array en forma de cuadrados, dividiendo la array en cuadrados o ciclos. Por ejemplo, 
una array de 4 X 4 tendrá 2 ciclos. El primer ciclo está formado por su 1ª fila, última columna, última fila y 1ª columna. El segundo ciclo está formado por 2ª fila, penúltima columna, penúltima fila y 2ª columna. La idea es para cada ciclo cuadrado, intercambiar los elementos involucrados con la celda correspondiente en la array en sentido contrario a las agujas del reloj, es decir, de arriba a izquierda, de izquierda a abajo, de abajo a la derecha y de derecha a arriba, uno a la vez usando nada más que un variable temporal para lograrlo.
Demostración: 
 

First Cycle (Involves Red Elements)
 1  2  3 4 
 5  6  7 8 
 9 10 11 12 
 13 14 15 16 

Moving first group of four elements (First
elements of 1st row, last row, 1st column 
and last column) of first cycle in counter
clockwise. 
 4  2  3 16
 5  6  7 8 
 9 10 11 12 
 1 14  15 13 
 
Moving next group of four elements of 
first cycle in counter clockwise 
 4  8  3 16 
 5  6  7  15  
 2  10 11 12 
 1  14  9 13 

Moving final group of four elements of 
first cycle in counter clockwise 
 4  8 12 16 
 3  6  7 15 
 2 10 11 14 
 1  5  9 13 


Second Cycle (Involves Blue Elements)
 4  8 12 16 
 3  6 7  15 
 2  10 11 14 
 1  5  9 13 

Fixing second cycle
 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13

Algoritmo: 
 

  1. Hay N/2 cuadrados o ciclos en una array de lado N. Procesa un cuadrado a la vez. Ejecute un ciclo para atravesar la array un ciclo a la vez, es decir, un ciclo de 0 a N/2 – 1, el contador de ciclo es i
  2. Considere los elementos en un grupo de 4 en el cuadro actual, gire los 4 elementos a la vez. Entonces, el número de tales grupos en un ciclo es N – 2*i.
  3. Así que ejecute un ciclo en cada ciclo de x a N – x – 1, el contador de ciclo es y
  4. Los elementos en el grupo actual son (x, y), (y, N-1-x), (N-1-x, N-1-y), (N-1-y, x), ahora gire el estos 4 elementos, es decir (x, y) <- (y, N-1-x), (y, N-1-x)<- (N-1-x, N-1-y), (N- 1-x, N-1-y)<- (N-1-y, x), (N-1-y, x)<- (x, y)
  5. Imprime la array.

Python3

# Python3 program to rotate a matrix by 90 degrees
N = 4
  
# An Inplace function to rotate 
# N x N matrix by 90 degrees in
# anti-clockwise direction
def rotateMatrix(mat):
      
    # Consider all squares one by one
    for x in range(0, int(N / 2)):
          
        # Consider elements in group   
        # of 4 in current square
        for y in range(x, N-x-1):
              
            # store current cell in temp variable
            temp = mat[x][y]
  
            # move values from right to top
            mat[x][y] = mat[y][N-1-x]
  
            # move values from bottom to right
            mat[y][N-1-x] = mat[N-1-x][N-1-y]
  
            # move values from left to bottom
            mat[N-1-x][N-1-y] = mat[N-1-y][x]
  
            # assign temp to left
            mat[N-1-y][x] = temp
  
  
# Function to print the matrix
def displayMatrix( mat ):
      
    for i in range(0, N):
          
        for j in range(0, N):
              
            print (mat[i][j], end = ' ')
        print ("")
      
      
  
  
# Driver Code
mat = [[0 for x in range(N)] for y in range(N)]
  
# Test case 1
mat = [ [1, 2, 3, 4 ],
        [5, 6, 7, 8 ],
        [9, 10, 11, 12 ],
        [13, 14, 15, 16 ] ]
          
'''
# Test case 2
mat = [ [1, 2, 3 ],
        [4, 5, 6 ],
        [7, 8, 9 ] ]
  
# Test case 3
mat = [ [1, 2 ],
        [4, 5 ] ]
          
'''
  
rotateMatrix(mat)
  
# Print rotated matrix
displayMatrix(mat)
  
  
# This code is contributed by saloni1297

Producción : 
 

 4  8 12 16 
 3  7 11 15 
 2  6 10 14 
 1  5  9 13 

Análisis de Complejidad: 
 

  • Complejidad de tiempo: O(n*n), donde n es el lado de la array. 
    Se necesita un solo recorrido de la array.
  • Complejidad espacial: O(1). 
    Como se necesita un espacio constante

Consulte el artículo completo sobre rotar la array cuadrada en el lugar 90 grados | ¡ Establezca 1 para más detalles!

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *