Rotate Image

Q: ¿Cuál es la complejidad temporal y espacial de rotar una matriz?

Rotar una matriz n × n lleva un tiempo O(n²), ya que casi todos los valores deben moverse una vez. El método de transponer y luego invertir necesita O(1) de espacio adicional. Crear una copia rotada también lleva un tiempo O(n²), pero usa O(n²) de espacio adicional.

MedioArrays y cadenas Matemáticas y simulación

+10

Se te proporciona una cuadrícula de enteros de n × n, una lista por fila. Gírala un cuarto de vuelta en sentido horario y devuélvela. La fila superior se convierte en la columna más a la derecha, la segunda fila en la columna a su izquierda, y así sucesivamente: el valor en (i, j) queda en (j, n-1-i). Puedes modificar la cuadrícula en el sitio; devuélvela.

Función

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: la cuadrícula cuadrada, una lista interna por fila
Devuelveinteger-2d-array: la matriz giró 90 grados en el sentido de las agujas del reloj

Restricciones

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Ejemplos

Entrada: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Salida: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Explicación: La primera fila, 3 7 1, se convierte en la última columna, leída de arriba abajo. La primera columna, 3 9 4, leída de abajo arriba, se convierte en la primera fila [4, 9, 3]. El valor central 5 se queda en su sitio.

Para ir más allá

¿Qué dos pasos in situ giran la matriz 180 grados, y puedes hacerlo en una sola pasada de intercambios?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

El lugar al que va cada valor se expresa mediante una fórmula: (i, j) pasa a (j, n-1-i). Lo difícil es mover los valores sin una segunda matriz, porque escribir un valor en su nueva celda sobrescribe uno que aún no se ha movido. Una transposición seguida de una inversión de filas produce el mismo giro de un cuarto mediante intercambios por pares.

Construye una copia rotada

Intuición

La fila i se convierte en la columna n-1-i, y el valor en la posición j de la fila termina en la posición j de esa columna, que es la fila j. Así que result[j][n-1-i] = matrix[i][j]. En el primer ejemplo, el 4 de la fila 2, columna 0, pasa a la fila 0, columna 0, por eso la respuesta empieza con 4.

Los valores se desplazan en ciclos de cuatro, así que escribir en el mismo lugar borraría un valor antes de que se desplazara: el 3 sobrescribiría el 1 de la esquina superior derecha. La copia cuesta n² celdas adicionales, 4,900 para n = 70.

Algoritmo

Crea una matriz de resultados n × n.
Para cada fila i y columna j, copia matrix[i][j] en result[j][n-1-i].
Devuelve el resultado.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Transpón y luego invierte cada fila

Intuición

Una transposición mueve (i, j) a (j, i), y al invertir una fila, la columna c pasa a ser la columna n-1-c. Juntas, estas operaciones trasladan (i, j) a (j, n-1-i), exactamente donde lo coloca la rotación.

Ambas operaciones se ejecutan en el mismo lugar porque cada una consiste en un conjunto de intercambios por pares. En una transposición, matrix[i][j] y matrix[j][i] deben ocupar la celda de la otra, así que un intercambio basta para ambas. Intercambia solo los pares con j > i, o cada par se intercambiará de nuevo y quedará como al principio. Al invertir una fila, se intercambian sus dos extremos y se avanza hacia el centro.

En el primer ejemplo, la transposición da [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: cada fila contiene ahora una antigua columna. Invertir cada fila da la respuesta.

La transposición realiza n(n-1)/2 intercambios y las inversiones, n·⌊n/2⌋, así que el trabajo es O(n²) y se usan unas pocas variables de memoria adicional. La versión en R primero copia la entrada en una matriz de R, así que su memoria adicional es O(n²).

Algoritmo

Para cada celda por encima de la diagonal principal, (i, j) con j > i, intercambia su valor con el de la celda (j, i).
Para cada fila, intercambia el primer y el último valor y avanza desde ambos extremos hacia el centro hasta que se encuentren.
Devuelve la matriz.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Errores comunes y casos límite

Transponer empezando con j en 0. Cada par se intercambia dos veces, lo que anula la transposición, así que el resultado solo invierte las filas: una imagen especular.
Invertir antes de transponer. Ese orden gira la matriz en sentido antihorario. Una prueba con una matriz de 2 × 2 lo detecta: [[1, 2], [3, 4]] debe convertirse en [[3, 1], [4, 2]].
Escribir matrix[j][n-1-i] = matrix[i][j] en la misma matriz. La celda de destino todavía contiene un valor que no se ha movido, y se pierde.
Usar n-i en lugar de n-1-i. Con índices basados en 0, la última columna es n-1, así que n-i se sale de los límites cuando i = 0.

Preguntas frecuentes3

¿Cuál es la complejidad temporal y espacial de rotar una matriz?

Rotar una matriz n × n lleva un tiempo O(n²), ya que casi todos los valores deben moverse una vez. El método de transponer y luego invertir necesita O(1) de espacio adicional. Crear una copia rotada también lleva un tiempo O(n²), pero usa O(n²) de espacio adicional.

¿Cómo se rota una matriz en sentido antihorario?

Intercambia el orden de los dos pasos: primero invierte cada fila y después transpón. También puedes transponer y después invertir el orden de las filas. De cualquier manera, el valor en (i, j) termina en (n-1-j, i).

¿Puedes rotar una matriz moviendo cuatro valores a la vez?

Sí. Cada valor fuera del centro pertenece a un ciclo de cuatro celdas: (i, j), (j, n-1-i), (n-1-i, n-1-j) y (n-1-j, i). Anillo por anillo, guarda un valor de cada ciclo en una variable y desplaza los otros tres. Tiene el mismo tiempo O(n²) y espacio O(1), con más operaciones aritméticas con índices que pueden salir mal.

def rotateImage(matrix):
    # Escribe el código aquí

Prueba #1

Prueba #2

Argumento

matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]

Salida Esperada

[[4, 9, 3], [8, 5, 7], [6, 2, 1]]