Défi LeetCode : Fusionner un tableau trié - Solution JavaScript

Meilleure interview 150

La fusion de tableaux triés est un problème classique, et comprendre comment le résoudre efficacement est essentiel pour coder les entretiens. Dans cet article, nous aborderons le 88. Merge Sorted Array de LeetCode, qui fait partie du défi Top Interview 150 Questions, en utilisant JavaScript. Plongeons dans le problème, ses nuances et une solution propre et optimale !

? Description du problème
Vous recevez deux tableaux d'entiers nums1 et nums2, triés par ordre non décroissant. Votre tâche consiste à fusionner nums2 en nums1, de telle sorte que nums1 reste trié.

Cependant, il y a une différence :

nums1 a suffisamment d'espace (défini sur 0) pour accueillir les éléments de nums2.
Le résultat final fusionné doit être stocké sur place dans nums1.

? Exemples

Exemple 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Exemple 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Exemple 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? Informations clés

• Fusion sur place : vous devez remplir nums1 sans utiliser d'espace supplémentaire. Cela signifie modifier directement le tableau.
• Stratégie vers l'arrière : étant donné que nums1 a un espace supplémentaire à la fin, l'approche la plus efficace consiste à le remplir par l'arrière.

? Solution JavaScript : approche en deux points

La solution optimale exploite une approche à deux points, en commençant par la fin des deux tableaux. Cela garantit que les éléments les plus grands sont placés en premier, évitant ainsi les déplacements inutiles des éléments.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

? Comment ça marche

1. Commencer par la fin :
   Comparez les plus grands éléments de nums1 et nums2 (en utilisant p1
   et pointeurs p2). Placez le plus grand élément à la fin de
   nums1 (en utilisant le pointeur p).

2. Pointeurs de décrémentation :
   Déplacez p1, p2 et p pendant que vous traitez les éléments.

3. Gérer les éléments restants :
   S'il reste des éléments dans nums2, copiez-les dans nums1. (Non
   devez copier les éléments de nums1, car ils sont déjà en place.)

? Analyse de complexité

? Essai à sec
Entrée :
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3

Étape p1 p2 p nums1
Init 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
Résultat final : [1,2,2,3,5,6]

? Essayez-le vous-même !

Découvrez le problème complet et les cas de test sur LeetCode. Mettez-vous au défi de mettre en œuvre la solution sans regarder le code !

✨ Conseils de pro pour les entretiens

1. Clarifiez les contraintes : demandez si vous pouvez utiliser de l'espace supplémentaire ou si la place est obligatoire.
2. Optimiser pour les cas extrêmes : considérez les cas où nums2 est vide ou nums1 n'a pas d'éléments initiaux (m = 0).
3. Parcourez votre logique : expliquez l'approche à deux points clairement à l'intervieweur.

Vous avez des questions ou des idées ? Partagez-les dans les commentaires ci-dessous ! Apprenons ensemble. ?

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!