Transpose Matrix

Q: ¿Cuál es la complejidad temporal de transponer una matriz?

O(m × n) : cada uno de los m × n valores se copia una vez, y nada menos puede producir la respuesta. La nueva matriz ocupa un espacio de O(m × n) , el tamaño de la salida en sí.

Q: ¿Puedes transponer una matriz in situ?

Para una matriz cuadrada, sí: intercambia matrix[i][j] por matrix[j][i] para cada celda por encima de la diagonal, con memoria adicional O(1) . Una matriz no cuadrada cambia de forma, así que, con una lista de filas, necesitas una matriz nueva.

PrincipianteArrays y cadenas

+10

Recibes una matriz de enteros como una lista de filas: matrix[i][j] es el valor de la fila i, columna j. Devuelve su transpuesta: el valor de la fila i, columna j pasa a la fila j, columna i, así que cada fila se convierte en una columna. La matriz no tiene que ser cuadrada: una matriz m × n se convierte en una de n × m.

Función

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

matrixinteger-2d-array: la matriz m × n, como una lista de m filas de n enteros
Devuelveinteger-2d-array: la transpuesta de n × m, como una lista de n filas de m enteros

Restricciones

1 ≤ m, n ≤ 1000, donde m = matrix.length y n = matrix[i].length
m × n ≤ 5000
Cada fila tiene la misma longitud n.
-1000 ≤ matrix[i][j] ≤ 1000

Ejemplos

Entrada: matrix = [[1, 2, 3], [4, 5, 6]]
Salida: [[1, 4], [2, 5], [3, 6]]
Explicación: La fila [1, 2, 3] se convierte en la primera columna y [4, 5, 6] en la segunda. Leído fila por fila, el resultado es [1, 4], [2, 5], [3, 6]: una matriz de 3 × 2.

Para ir más allá

Supón que la matriz está almacenada como una sola matriz plana de m × n valores, fila tras fila. ¿Puedes transponer una matriz no cuadrada dentro de esa matriz, sin usar una segunda matriz?

Pistas

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

0 de 3 abiertas

Solución

La transposición no calcula nada: el valor en (i, j) pasa a (j, i). El trabajo consiste en cambiar la forma. El resultado tiene n filas de longitud m, así que una lista de filas no cuadrada no se puede transponer en el sitio; crea una matriz nueva con las dimensiones intercambiadas y rellénala.

Lee la matriz columna por columna

Intuición

La fila j de la respuesta es la columna j de la entrada, leída de arriba abajo. Para [[1, 2, 3], [4, 5, 6]], la columna 0 se lee como 1 y después 4, así que la primera fila de la respuesta es [1, 4].

Cada valor se lee una vez y se escribe una vez: tiempo O(m × n) y espacio O(m × n) para el resultado. Al construir cada fila nueva, se salta entre todas las filas de entrada en lugar de leer a lo largo de una sola, que es la forma más lenta de recorrer la memoria.

Algoritmo

Sea m el número de filas y n la longitud de una fila.
Para cada columna j, desde 0 hasta n-1, inicia una lista vacía.
Añade matrix[i][j] a ella para cada i, desde 0 hasta m-1.
Añade la lista al resultado como fila j y devuelve el resultado después de la última columna.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Rellena una nueva cuadrícula de n × m reflejando cada celda

Intuición

Crea de antemano el resultado n × m, después lee la entrada en el orden en que está almacenada, fila por fila, y coloca cada valor en su dirección reflejada: result[j][i] = matrix[i][j]. Esto es correcto porque una transposición consiste exactamente en intercambiar los índices de esta manera, una vez por cada celda.

Cada valor se copia una vez, así que el tiempo es O(m × n), y la cuadrícula ocupa el espacio O(m × n) que la salida necesita de todos modos. Leer por filas recorre la memoria en el orden en que está almacenada, y cada fila del resultado se asigna una sola vez con su tamaño final.

Algoritmo

Sea m el número de filas y n la longitud de una fila.
Crea result con n filas, cada una con m valores.
Para cada fila i y cada columna j de la entrada, establece result[j][i] = matrix[i][j].
Devuelve result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

Errores comunes y casos límite

Construir el resultado con la misma forma que la entrada. Para el ejemplo de 2 × 3, escribir result[2][0] se sale de los límites: el resultado necesita n filas de longitud m.
Intercambiar matrix[i][j] por matrix[j][i] en el mismo sitio. Eso solo funciona cuando m = n y únicamente para las celdas con j > i; un bucle que recorra todas las celdas intercambia cada par dos veces y devuelve la matriz sin cambios.
En Python, [[0] * m] * n crea n referencias a una misma lista, por lo que al escribir en una celda se escribe en toda una columna. Construye cada fila por separado.
En C, quien llama lee *returnSize como el número de filas del resultado, n, y (*returnColumnSizes)[j] como la longitud de cada fila, m.

Preguntas frecuentes3

¿Qué es la transpuesta de una matriz?

Es la matriz que obtienes al intercambiar filas y columnas: el valor de la fila i, columna j pasa a la fila j, columna i. Una matriz 2 × 3 se convierte en una 3 × 2, y al transponerla dos veces se obtiene de nuevo la matriz original.

¿Cuál es la complejidad temporal de transponer una matriz?

O(m × n): cada uno de los m × n valores se copia una vez, y nada menos puede producir la respuesta. La nueva matriz ocupa un espacio de O(m × n), el tamaño de la salida en sí.

¿Puedes transponer una matriz in situ?

Para una matriz cuadrada, sí: intercambia matrix[i][j] por matrix[j][i] para cada celda por encima de la diagonal, con memoria adicional O(1). Una matriz no cuadrada cambia de forma, así que, con una lista de filas, necesitas una matriz nueva.

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

Prueba #1

Prueba #2

Argumento

matrix = [[1, 2, 3], [4, 5, 6]]

Salida Esperada

[[1, 4], [2, 5], [3, 6]]