Transpose Matrix

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

C’est O(m × n) , car chacune des m × n valeurs est copiée une fois et rien de moins ne peut produire le résultat. La nouvelle matrice occupe un espace de O(m × n) , ce qui correspond à la taille de la sortie elle-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, en utilisant O(1) mémoire supplémentaire. Pour une matrice non carrée, le résultat a une forme différente ; avec une liste de lignes, vous avez donc besoin d’une nouvelle matrice.

Q: Comment transposer une matrice non carrée ?

Crée un résultat avec n lignes de longueur m , alors que l’entrée comporte m lignes de longueur n . Copie ensuite chaque valeur avec result[j][i] = matrix[i][j] . L’idée de la diagonale du cas carré ne s’applique pas, car les deux matrices n’ont pas la même forme.

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 matrice obtenue en transformant chaque ligne en colonne. La valeur située à la ligne i, colonne j passe à la ligne j, colonne i. 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 de dimensions 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 première ligne [1, 2, 3] devient la première colonne et [4, 5, 6] la deuxième. En lisant le résultat ligne par ligne, on obtient [1, 4], [2, 5], [3, 6] : la matrice 2 × 3 est devenue une matrice 3 × 2.

+15 tests cachés à la soumission

Pour aller plus loin

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

Indices

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

0 sur 3 ouverts

Solution

La transposition est un simple changement d’adresse : la valeur à (i, j) passe à (j, i), et aucun calcul n’est effectué. Le travail consiste à obtenir la bonne forme. Une matrice non carrée stockée sous forme de liste de lignes ne peut pas être transposée sur place, car le résultat comporte n lignes de longueur m au lieu de m lignes de longueur n ; il faut donc créer une nouvelle matrice de dimensions inversées et la remplir.

Parcourez la matrice colonne par colonne

Intuition

La ligne j de la réponse est la colonne j de l’entrée, lue de haut en bas. Construis donc la réponse une ligne à la fois : pour chaque colonne j de 0 à n-1, récupère matrix[0][j], matrix[1][j], et ainsi de suite jusqu’à matrix[m-1][j], puis ajoute cette liste comme ligne suivante.

Pour [[1, 2, 3], [4, 5, 6]], la colonne 0 donne 1 puis 4, la colonne 1 donne 2 puis 5, et la colonne 2 donne 3 puis 6. La réponse est [[1, 4], [2, 5], [3, 6]], avec n = 3 lignes de m = 2 valeurs.

Chaque valeur est lue une fois et écrite une fois, le temps d’exécution est donc O(m × n) et le résultat occupe O(m × n) d’espace. Le coût vient du schéma d’accès : construire une nouvelle ligne touche chaque ligne de la matrice d’entrée, en passant d’une ligne à l’autre au lieu de lire le long d’une même ligne.

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

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

Intuition

Détermine d’abord la forme, puis remplis la grille. La réponse comporte n lignes de longueur m ; crée donc cette grille dès le départ. Lis ensuite l’entrée dans son ordre naturel, ligne par ligne et de gauche à droite, et place chaque valeur à son adresse symétrique : result[j][i] = matrix[i][j].

La règle est correcte, car transposer consiste exactement à permuter les deux indices. Dans l’exemple carré [[1, 2], [3, 4]], les valeurs 1 et 4 sur la diagonale restent à leur place, 2 passe de (0, 1) à (1, 0), et 3 de (1, 0) à (0, 1), ce qui donne [[1, 3], [2, 4]].

Chacune des m × n valeurs est copiée une fois : le temps d’exécution est donc O(m × n), et la nouvelle grille occupe l’espace O(m × n) dont la sortie a de toute façon besoin. Lire l’entrée ligne par ligne parcourt la mémoire dans l’ordre où elle est stockée, et chaque ligne du résultat est créée une 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

Presque toutes les mauvaises réponses viennent de la forme, et non des valeurs.

Construire le résultat avec la forme d’origine. Un résultat de m lignes et n colonnes ne fonctionne que pour une entrée carrée ; pour l’exemple 2 × 3, écrire result[2][0] dépasse les limites. Le résultat doit comporter n lignes de longueur m.
Échanger les éléments en place dans une matrice non carrée. Échanger matrix[i][j] avec matrix[j][i] ne fonctionne que lorsque m = n, et même dans ce cas, la boucle ne doit parcourir que les cellules au-dessus de la diagonale (j > i), sinon chaque paire est échangée deux fois et la matrice revient à son état initial.
Partager un même objet ligne. En Python, [[0] * m] * n crée n références vers la même liste, donc écrire dans une cellule modifie toute la colonne. Construisez chaque ligne séparément.
Oublier les tailles des colonnes 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équentes4

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

C’est la matrice que vous obtenez 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 ?

C’est O(m × n), car chacune des m × n valeurs est copiée une fois et rien de moins ne peut produire le résultat. La nouvelle matrice occupe un espace de O(m × n), ce qui correspond à la taille de la sortie elle-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, en utilisant O(1) mémoire supplémentaire. Pour une matrice non carrée, le résultat a une forme différente ; avec une liste de lignes, vous avez donc besoin d’une nouvelle matrice.

Comment transposer une matrice non carrée ?

Crée un résultat avec n lignes de longueur m, alors que l’entrée comporte m lignes de longueur n. Copie ensuite chaque valeur avec result[j][i] = matrix[i][j]. L’idée de la diagonale du cas carré ne s’applique pas, car les deux matrices n’ont pas la même forme.

Python

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

Cas de test

Cas 1

Cas 2

Entrée

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

Attendu

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