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:
- 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
- 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.
- Así que ejecute un ciclo en cada ciclo de x a N – x – 1, el contador de ciclo es y
- 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)
- 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