Transpose Matrix

Q: Quelle est la complexité temporelle de la transposition d’une matrice ?

O(m × n) : chacune des m × n valeurs est copiée une fois, et rien de moins ne peut produire la réponse. La nouvelle matrice occupe un espace de O(m × n) , soit la taille du résultat lui-même.

Q: Peux-tu transposer une matrice sur place ?

Pour une matrice carrée, oui : échangez matrix[i][j] avec matrix[j][i] pour chaque cellule au-dessus de la diagonale, avec une mémoire supplémentaire en O(1) . Une matrice non carrée change de forme ; avec une liste de lignes, il vous faut donc une nouvelle matrice.

DébutantTableaux et chaînes

+10

Tu reçois une matrice d’entiers sous forme de liste de lignes : matrix[i][j] est la valeur de la ligne i, colonne j. Renvoie sa transposée : la valeur située à la ligne i, colonne j passe à la ligne j, colonne i, de sorte que chaque ligne devient une colonne. La matrice n’a pas besoin d’être carrée : une matrice m × n devient une matrice n × m.

Fonction

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

matrixinteger-2d-array: la matrice m × n, sous forme d’une liste de m lignes de n entiers
Renvoieinteger-2d-array: la transposée n × m, sous forme d’une liste de n lignes de m entiers

Contraintes

1 ≤ m, n ≤ 1000, où m = matrix.length et n = matrix[i].length
m × n ≤ 5000
Chaque ligne a la même longueur n.
-1000 ≤ matrix[i][j] ≤ 1000

Exemples

Entrée: matrix = [[1, 2, 3], [4, 5, 6]]
Sortie: [[1, 4], [2, 5], [3, 6]]
Explication: La ligne [1, 2, 3] devient la première colonne et [4, 5, 6] la deuxième. En lisant ligne par ligne, le résultat est [1, 4], [2, 5], [3, 6] : une matrice de 3 × 2.

Pour aller plus loin

Supposons que la matrice soit stockée dans un tableau plat contenant m × n valeurs, ligne après ligne. Peux-tu transposer une matrice non carrée directement dans ce tableau, sans utiliser de second tableau ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La transposition ne calcule rien : la valeur en (i, j) passe en (j, i). Tout se joue dans la forme. Le résultat comporte n lignes de longueur m, donc une liste de lignes non carrée ne peut pas être transposée sur place ; crée une nouvelle matrice de dimensions inversées et remplis-la.

Lis la matrice colonne par colonne

Intuition

La ligne j de la réponse correspond à la colonne j de l’entrée, lue de haut en bas. Pour [[1, 2, 3], [4, 5, 6]], la colonne 0 donne 1 puis 4, donc la première ligne de la réponse est [1, 4].

Chaque valeur est lue une fois et écrite une fois : un temps de O(m × n) et un espace de O(m × n) pour le résultat. La construction de chaque nouvelle ligne parcourt toutes les lignes d’entrée au lieu d’en lire une seule, ce qui est la façon la plus lente de parcourir la mémoire.

Algorithme

Soit m le nombre de lignes et n la longueur d’une ligne.
Pour chaque colonne j de 0 à n-1, commencez par une liste vide.
Ajoutez-y matrix[i][j] pour chaque i de 0 à m-1.
Ajoutez la liste au résultat comme ligne j, puis renvoyez le résultat après la dernière colonne.

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

Remplir une nouvelle grille n × m en reflétant chaque cellule

Intuition

Créez le résultat n × m à l’avance, puis lisez l’entrée dans l’ordre où elle est stockée, ligne par ligne, et placez chaque valeur à son adresse symétrique : result[j][i] = matrix[i][j]. C’est correct, car une transposition consiste exactement à permuter les indices, une fois pour chaque cellule.

Chaque valeur est copiée une fois, donc le temps d’exécution est O(m × n), et la grille occupe l’espace O(m × n) dont la sortie a de toute façon besoin. Lire les lignes les unes après les autres parcourt la mémoire dans l’ordre où elle est stockée, et chaque ligne du résultat est allouée une seule fois à sa taille finale.

Algorithme

Soit m le nombre de lignes et n la longueur d’une ligne.
Créez result avec n lignes, chacune contenant m valeurs.
Pour chaque ligne i et chaque colonne j de l’entrée, définissez result[j][i] = matrix[i][j].
Renvoyez 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

Pièges et cas limites

Construire le résultat avec les dimensions de l’entrée. Pour l’exemple 2 × 3, écrire result[2][0] dépasse la fin : le résultat doit comporter n lignes de longueur m.
Échanger matrix[i][j] avec matrix[j][i] sur place. Cela ne fonctionne que lorsque m = n, et uniquement pour les cellules où j > i ; une boucle sur chaque cellule échange chaque paire deux fois et laisse la matrice inchangée.
En Python, [[0] * m] * n crée n références vers une seule liste, donc écrire dans une cellule modifie toute une colonne. Construis chaque ligne séparément.
En C, l’appelant lit *returnSize comme le nombre de lignes du résultat, n, et (*returnColumnSizes)[j] comme la longueur de chaque ligne, m.

Questions fréquentes3

Qu’est-ce que la transposée d’une matrice ?

C’est la matrice que l’on obtient en échangeant les lignes et les colonnes : la valeur à la ligne i, colonne j passe à la ligne j, colonne i. Une matrice 2 × 3 devient 3 × 2, et effectuer la transposition deux fois redonne la matrice d’origine.

Quelle est la complexité temporelle de la transposition d’une matrice ?

O(m × n) : chacune des m × n valeurs est copiée une fois, et rien de moins ne peut produire la réponse. La nouvelle matrice occupe un espace de O(m × n), soit la taille du résultat lui-même.

Peux-tu transposer une matrice sur place ?

Pour une matrice carrée, oui : échangez matrix[i][j] avec matrix[j][i] pour chaque cellule au-dessus de la diagonale, avec une mémoire supplémentaire en O(1). Une matrice non carrée change de forme ; avec une liste de lignes, il vous faut donc une nouvelle matrice.

def transpose(matrix):
    # Écrivez le code ici

Test #1

Test #2

Argument

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

Résultat attendu

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