Transpose Matrix

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

Es O(m × n) , porque 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) , que es el tamaño de la propia salida.

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, usando memoria adicional O(1) . Para una matriz no cuadrada, el resultado tiene una forma diferente, así que con una lista de filas necesitas una matriz nueva.

Q: ¿Cómo se transpone una matriz no cuadrada?

Crea un resultado con n filas de longitud m , donde la entrada tiene m filas de longitud n . Después copia cada valor con result[j][i] = matrix[i][j] . La idea de la diagonal del caso cuadrado no se aplica, porque las dos matrices no tienen la misma forma.

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, la matriz que obtienes al convertir cada fila en una columna. El valor de la fila i, columna j pasa a la fila j, columna i. La matriz no tiene que ser cuadrada: una matriz de 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 primera fila [1, 2, 3] se convierte en la primera columna y [4, 5, 6] en la segunda. Al leer el resultado fila por fila, se obtiene [1, 4], [2, 5], [3, 6]: la matriz de 2 × 3 se convirtió en una de 3 × 2.

+15 pruebas ocultas al enviar

Para ir más allá

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

Pistas

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

0 de 3 abiertas

Solución

Transponer es un simple cambio de posición: el valor en (i, j) pasa a (j, i), y no se calcula nada. El trabajo consiste en obtener la forma correcta. Una matriz no cuadrada almacenada como una lista de filas no se puede transponer in situ, porque el resultado tiene n filas de longitud m en lugar de m filas de longitud n, así que construyes una matriz nueva con las dimensiones intercambiadas y la rellenas.

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. Así que construye la respuesta una fila a la vez: para cada columna j desde 0 hasta n-1, recoge matrix[0][j], matrix[1][j], y así sucesivamente hasta matrix[m-1][j], y añade esa lista como la siguiente fila.

Para [[1, 2, 3], [4, 5, 6]], la columna 0 se lee como 1 después 4, la columna 1 como 2 después 5, la columna 2 como 3 después 6. La respuesta es [[1, 4], [2, 5], [3, 6]], con n = 3 filas de m = 2 valores.

Cada valor se lee una vez y se escribe una vez, así que el tiempo es O(m × n) y el resultado ocupa O(m × n) espacio. El coste está en el patrón de acceso: construir una fila nueva toca todas las filas de entrada, saltando de una fila a otra en vez de leer siguiendo una sola.

Algoritmo

Sea m el número de filas y n la longitud de una fila.
Para cada columna j, desde 0 hasta n-1, empieza con 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

Decide primero la forma y después rellénala. La respuesta tiene n filas de longitud m, así que crea esa cuadrícula de antemano. Después, lee la entrada en su orden natural, fila por fila y de izquierda a derecha, y coloca cada valor en su posición reflejada: result[j][i] = matrix[i][j].

La regla es correcta porque transponer consiste exactamente en intercambiar los dos índices. En el ejemplo cuadrado [[1, 2], [3, 4]], los valores 1 y 4 de la diagonal quedan donde estaban, el 2 pasa de (0, 1) a (1, 0), y el 3 pasa de (1, 0) a (0, 1), lo que da [[1, 3], [2, 4]].

Cada uno de los m × n valores se copia una vez, así que el tiempo es O(m × n), y la nueva cuadrícula ocupa el espacio O(m × n) que la salida necesita de todos modos. Leer la entrada por filas recorre la memoria en el orden en que está almacenada, y cada fila del resultado se crea 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

Casi todas las respuestas incorrectas se deben a la forma, no a los valores.

Construir el resultado con la forma original. Un resultado de m filas y n columnas solo funciona con una entrada cuadrada; para el ejemplo de 2 × 3, escribir result[2][0] se sale del límite. El resultado necesita n filas de longitud m.
Intercambiar elementos in situ en una matriz no cuadrada. Intercambiar matrix[i][j] con matrix[j][i] solo funciona cuando m = n, e incluso entonces el bucle debe abarcar solo las celdas por encima de la diagonal (j > i), o cada par se intercambiará dos veces y la matriz quedará como estaba.
Compartir un mismo objeto de fila. En Python, [[0] * m] * n crea n referencias a la misma lista, así que escribir en una celda escribe en toda la columna. Crea cada fila por separado.
Olvidar los tamaños de las columnas en C. El código que llama lee *returnSize como el número de filas del resultado, n, y (*returnColumnSizes)[j] como la longitud de cada fila, m.

Preguntas frecuentes4

¿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 3 × 2, y transponerla dos veces devuelve la matriz original.

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

Es O(m × n), porque 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), que es el tamaño de la propia salida.

¿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, usando memoria adicional O(1). Para una matriz no cuadrada, el resultado tiene una forma diferente, así que con una lista de filas necesitas una matriz nueva.

¿Cómo se transpone una matriz no cuadrada?

Crea un resultado con n filas de longitud m, donde la entrada tiene m filas de longitud n. Después copia cada valor con result[j][i] = matrix[i][j]. La idea de la diagonal del caso cuadrado no se aplica, porque las dos matrices no tienen la misma forma.

Python

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

Casos de prueba

Caso 1

Caso 2

Entrada

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

Esperado

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