Comment pouvons-nous fusionner efficacement deux tableaux triés ?

Fusionner efficacement des tableaux triés : une méthode améliorée

Pour fusionner deux tableaux triés en un seul tableau trié, plusieurs approches de programmation peuvent être utilisées. Cependant, l'une des techniques les plus efficaces et fréquemment recommandées est la suivante :

Cet algorithme parcourt simultanément les deux tableaux, en comparant les éléments de chaque index actuel et en ajoutant le plus petit élément au tableau de sortie. Ce processus se poursuit jusqu'à ce que l'une des baies soit épuisée. Tous les éléments restants dans l'autre tableau sont ensuite ajoutés.

Voici un exemple d'implémentation optimisée de cet algorithme en Java :

public static int[] merge(int[] a, int[] b) {

    int[] answer = new int[a.length + b.length];
    int i = 0, j = 0, k = 0;

    while (i < a.length && j < b.length)
        answer[k++] = a[i] < b[j] ? a[i++] : b[j++];

    while (i < a.length)
        answer[k++] = a[i++];

    while (j < b.length)
        answer[k++] = b[j++];

    return answer;
}

Cette approche a une complexité temporelle de O(n m ), où n et m représentent respectivement les longueurs des tableaux a et b. Cette version améliorée élimine les contrôles inutiles d'épuisement et utilise une construction de boucle while compacte pour une fusion efficace.

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!