L'intersection de deux tableaux triés

Utilisation set_intersection comme ici. L'habituelle mise en œuvre des travaux semblables à la fusion de la partie de fusion-algorithme de tri.

OriginalL'auteur amit_grepclub

J'ai été aux prises avec le même problème pour un certain temps maintenant, jusqu'à présent, je suis venu avec:

1. Linéaire correspondant qui permettra de O(m+n) dans le pire cas. En gros, vous gardez les deux pointeurs (A et B), chacune pointant vers le début de chaque tableau. Alors, avance le pointeur qui pointe à la valeur la plus petite, jusqu'à ce que vous atteignez la fin de l'un des tableaux, qui indiquent pas d'intersection. À tout moment, si vous avez * = = *B - voici votre intersection.

2. Binaire correspondant. Ce qui donne ~ O(n*log(m)) dans le pire cas. En gros, vous choisissez plus petit tableau et effectuer une recherche binaire dans l'ensemble de tous les éléments de la plus petite matrice. Si vous souhaitez plus de fantaisie, vous pouvez même utiliser la dernière position où binaire echec de la recherche et de l'utiliser comme point de départ pour la prochaine binaire de recherche. De cette façon, vous améliorer de façon marginale pire des cas, mais pour certains jeux, il peut accomplir des miracles 🙂

3. Double binaire correspondant. C'est une variation régulière binaire correspondant. Fondamentalement, vous obtenez l'élément à partir du milieu de la plus petite matrice et faire de la recherche binaire dans l'ensemble. Si vous ne trouvez rien, alors vous couper petit tableau en deux (et oui, vous pouvez jeter élément que vous avez déjà utilisé) et coupez les plus grosses tableau en deux (utiliser les binaires de recherche de point de défaillance). Et puis répétez l'opération pour chaque paire. Les résultats sont mieux que O(n*log(m)) mais je suis trop paresseux pour calculer ce qu'ils sont.

Ceux sont les deux les plus de base. Les deux ont des mérites. Linéaire est un peu plus facile à mettre en œuvre. Binaire est sans doute plus rapide (bien qu'il existe beaucoup de cas, quand linéaire correspondant sera mieux binaire).

Si quelqu'un sait quelque chose de mieux que ce que j'aimerais entendre. Correspondance des tableaux est ce que je fais ces jours-ci.

P. S. ne pas me citer sur les termes "linéaire correspondant" et "binaire correspondant" comme je les ai faites moi-même et il y a probablement nom de fantaisie pour elle déjà.

OriginalL'auteur Nazar

Considérons deux tableaux triés: -

int[] array1 = {1,2,3,4,5,6,7,8};
int[] array2 = {2,4,8};

int i=0, j=0;    //taken two pointers

Tandis que la boucle sera exécutée jusqu'à deux pointeurs atteindre les longueurs respectives.

while(i<array1.length || j<array2.length){
    if(array1[i] > array2[j])     //if first array element is bigger then increment 2nd pointer
       j++;
    else if(array1[i] < array2[j]) //same checking for second array element
      i++;
    else {                         //if both are equal then print them and increment both pointers
        System.out.print(a1[i]+ " ");

        if(i==a1.length-1 ||j==a2.length-1)   //one additional check for ArrayOutOfBoundsException
            break;
        else{
            i++;
            j++;
        }
    }
}        

Sortie sera: -

2 4 8

OriginalL'auteur Kushal Shinde