Faire pivoter sans effort une matrice en place : un guide complet

La rotation d'une matrice de 90 degrés dans le sens des aiguilles d'une montre est un problème courant en informatique et lors des entretiens techniques. Ce problème peut être particulièrement intéressant car le but est d'effectuer la rotation sur place, sans utiliser de mémoire supplémentaire pour une nouvelle matrice. Dans ce guide, nous explorerons comment y parvenir avec une explication claire et un exemple de code.

Description du problème

On vous donne une matrice 2D n x n A représentant une image. Votre tâche consiste à faire pivoter l'image dans le sens des aiguilles d'une montre à 90 degrés sur place. Si vous utilisez une baie supplémentaire, vous ne recevrez qu'un crédit partiel.

Contraintes du problème

1≤n≤1000

Format d'entrée

Une matrice 2D A d'entiers

Format de sortie

La matrice pivotée 2D

Exemple d'entrée

[
    [1, 2],
    [3, 4]
]

Exemple de sortie

[
    [3, 1],
    [4, 2]
]

Exemple d'explication

Après avoir fait pivoter la matrice de 90 degrés :

• 1 passe en position 2
• 2 passe en position 4
• 4 passe à la position 3
• 3 passe à la position 1

Solution étape par étape

Étape 1 : Transposer la matrice

• Transposer une matrice signifie convertir ses lignes en colonnes et ses colonnes en lignes. Cela peut être fait en échangeant des éléments sur la diagonale principale (diagonale supérieure gauche à inférieure droite).

Étape 2 : inverser chaque ligne

• Une fois la matrice transposée, l'étape suivante consiste à inverser chaque ligne. Cela fera effectivement pivoter la matrice de 90 degrés dans le sens des aiguilles d'une montre.

Exemple de code

Voici une fonction JavaScript pour effectuer la rotation :

function rotateMatrix(A) {
    const n = A.length;

    // Step 1: Transpose the matrix
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            let temp = A[i][j];
            A[i][j] = A[j][i];
            A[j][i] = temp;
        }
    }

    // Step 2: Reverse each row
    for (let i = 0; i < n; i++) {
        A[i].reverse();
    }

    return A;
}

// Example usage:
let matrix = [
    [1, 2],
    [3, 4]
];

console.log(rotateMatrix(matrix));

Explication du Code

Transposez la matrice :

• Parcourez la matrice en utilisant deux boucles imbriquées.
• Échangez les éléments A[i][j] et A[j][i] pour transposer la matrice.

Inversez chaque ligne :

• Utilisez la méthode reverse() intégrée pour inverser chaque ligne de la matrice transposée.

Renvoyez la matrice pivotée :

• Après avoir transposé et inversé chaque ligne, la matrice est tournée de 90 degrés dans le sens des aiguilles d'une montre.

Conclusion

La rotation d'une matrice sur place est une compétence précieuse qui met en valeur votre compréhension de la manipulation des tableaux et des algorithmes sur place. En transposant la matrice puis en inversant chaque ligne, vous pouvez obtenir la rotation souhaitée sans utiliser d'espace supplémentaire. Pratiquez cette méthode pour améliorer vos capacités de résolution de problèmes lors des entretiens techniques et des défis de codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!