Fusion de deux tableaux triés (LeetCode 88)

L'objectif est de fusionner deux tableaux d'entiers triés, nums1 et nums2, en un seul tableau trié au sein de nums1. Pour optimiser l'espace, nous utilisons une approche à trois pointeurs partant de la fin des tableaux, ce qui évite d'utiliser une structure de données intermédiaire.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int p1 = m - 1;      // Index du dernier élément significatif de nums1
        int p2 = n - 1;      // Index du dernier élément de nums2
        int pWrite = m + n - 1; // Position d'écriture à la fin de nums1

        while (p2 >= 0) {
            // Si nums1 a encore des éléments et que sa valeur est supérieure à celle de nums2
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[pWrite--] = nums1[p1--];
            } else {
                // Sinon, on place l'élément de nums2
                nums1[pWrite--] = nums2[p2--];
            }
        }
    }
};

Le fonctionnement de cet algorithme repose sur les étapes suivantes :

• Initialisation : On définit trois curseurs : un pour la fin des données réelles de nums1, un pour nums2, et un pour l'emplacement final du tableau fusionné.
• Boucle de comparaison : On compare les éléments depuis la fin. Le plus grand est placé à la dernière position disponible de nums1. Cela garantit qu'aucun élément non traité de nums1 ne soit écrasé.
• Gestion du reliquat : Si nums2 contient encore des éléments après que nums1 a été parcouru (p1 < 0), ces éléments sont copiés directement. Si p2 arrive à zéro en premier, le reste de nums1 est déjà à la bonne place.

Concepts fondamentaux : Pointeurs et Références

En C++, la gestion de la mémoire et le passage de paramètres reposent sur les notions de pointeurs et de références.

Le Pointeur : Définition et usages

Un pointeur est une variable dont la valeur est l'adresse mémoire d'une autre variable. Ses appplications sont multiples :

• Allocation dynamique : Permet de réserver de la mémoire sur le tas (heap) via new et de la libérer avec delete. Cela offre une flexibilité totale sur la durée de vie des objets.
• Structures de données complexes : Indispensable pour créer des listes chaînées, des arbres ou des graphes où chaque nœud contient l'adresse du nœud suivant.
• Polymorphisme : En programmation orientée objet, un pointeur de classe de base peut pointer vers une instance d'une classe dérivée, permettant l'appel de méthodes virtuelles.

// Exemple de polymorphisme
class Forme {
public:
    virtual void dessiner() { cout << "Forme générique" << endl; }
};

class Cercle : public Forme {
public:
    void dessiner() override { cout << "Cercle" << endl; }
};

Forme* maForme = new Cercle();
maForme->dessiner(); // Affiche "Cercle"
delete maForme;

Distinction entre Référence et Pointeur

Bien que les deux permettent d'accéder à une donnée distante, leurs comportements diffèrent sur plusieurs points essentiels :

1. Nullité : Un pointeur peut être nul (nullptr), alors qu'une référence doit toujours être liée à un objet existant.
2. Initialisation : Une référence doit obligatoirement être initialisée lors de sa déclaration. Un pointeur peut être déclaré sans être assigné immédiatement.
3. Réassignation : Un pointeur peut changer de cible durant l'exécution. Une référence, une fois liée, ne peut plus pointer vers un autre objet ; elle agit comme un alias permanent.
4. Syntaxe : L'utilisation d'une référence est plus naturelle car elle ne nécessite pas l'opérateur de déréférencement (*) pour accéder à la valeur.
5. Sécurité : Les références sont généralement plus sûres car elles limitent les risques liés aux pointeurs sauvages (wild pointers) ou aux accès mémoire invalides.