Comment croiser deux tableaux entiers triés sans doublons?

C'est une question d'entrevue que j'utilise comme un exercice de programmation.

D'entrée: Deux triés entier matrices A et B dans l'ordre croissant et de différentes tailles N et M, respectivement

De sortie: triés tableau d'entiers C dans l'ordre croissant, qui contient des éléments qui apparaissent à la fois dans A et B

Contraintes: Pas les doublons sont autorisés dans C

Exemple: Pour l'entrée A = {3,6,8,9} et B = {4,5,6,9,10,11}, la sortie doit être C = {6,9}

Merci pour vos réponses à tous! Pour résumer, il existe deux principales approches à ce problème:

Ma solution originale était de garder les deux pointeurs, l'un pour chaque tableau, et la numérisation des matrices de gauche à droite de façon interchangeable, tout en reprenant les éléments qui correspondent. Ainsi, lorsque nous l'élément courant d'un tableau est plus grand que le second tableau, nous gardons l'incrémentation du pointeur de la deuxième rangée jusqu'à nous, l'actuel premier élément de tableau ou le viaduc (trouver un plus). Je garde tous appariés dans un tableau séparé, qui est retourné une fois que nous arrivons à la fin d'une des entrées des tableaux.

Une autre façon que nous pourrions faire, c'est de scanner l'un des tableaux de façon linéaire, en utilisant binaire de recherche pour trouver une correspondance dans le second tableau. Cela voudrait dire O(N*log(M)), si l'on analyse Un et pour chacun de ses de N éléments binaires de recherche sur B (O(log(M)) de temps).

J'ai mis en place les deux approches et mené une expérience pour voir comment les deux se comparer (plus de détails sur ce qui peut être trouvé ici). La méthode de Recherche Binaire semble gagner lorsque M est d'environ 70 fois plus grand que N, lorsque N est 1 millions d'éléments.

source d'informationauteur Artur Galiullin | 2012-02-10

  1. 5

    Ce problème réduit essentiellement à un rejoindre opération, puis une filtre opération (pour supprimer les doublons et de ne garder intérieure matches).

    Que les entrées sont déjà triés, la jointure peut être réalisée de manière efficace par le biais d'un jointure de fusionavec O(taille(a) + taille(b)).

    La filtre de l'opération de O(n) car la sortie de la jointure est trié et à supprimer les doublons tout ce que vous avez à faire est de vérifier si chaque élément est la même que celle qui la précède. Filtrage uniquement à l'intérieur des matchs est trivial, vous venez de jeter tous les éléments qui n'ont pas été appariés (les jointures externes).

    Il existe des possibilités de parallélisme (les deux à la jointure et le filtre) pour obtenir de meilleures performances. Par exemple, le Apache Pig cadre sur Hadoop offre un en parallèle de la mise en œuvre une jointure de fusion.

    Il y a d'évidentes compromis entre performance et complexité (et donc la facilité de maintenance). Donc, je dirais une bonne réponse à une question d'entrevue a vraiment besoin de prendre en compte les exigences de performance.

    • Défini en fonction de la comparaison, O(nlogn) - Relativement lent, très simple, utilisez si il n'y a aucun soucis de performance. La simplicité l'emporte.

    • Jointure de fusion + Filtre - O(n) - Rapide, sujette à erreur de codage, utilisation si
      la performance est un problème. Idéalement, essayez d'utiliser une bibliothèque existante pour ce faire, ou peut-être même utiliser une base de données le cas échéant.

    • Parallèles de mise en Œuvre - O(n/p) - Très
      rapide, nécessite d'autres infrastructures en place, utiliser si le volume est
      très grand et devrait croître et c'est une grande performance
      goulot d'étranglement.

    (À noter également que la fonction en question intersectSortedArrays est essentiellement une modification de la jointure de fusion, où le filtre est réalisé lors de la jointure. Vous pouvez filtrer par la suite, sans perte de performances, bien qu'une légère augmentation de la quantité de mémoire).

    Dernière pensée.

    En fait, je soupçonne que la plupart des commerciaux modernes Sgbdr offre fil du parallélisme dans leur mise en œuvre de jointures, de sorte que la version Hadoop offre est la machine de parallélisme au niveau de l' (distribution). À partir d'une conception de point de vue, peut-être une bonne solution simple à cette question est de mettre les données dans une base de données, index sur A et B (en réalité, le tri des données) et l'utilisation d'un SQL jointure interne.

  2. 6

    Comment sur:

    public static int[] intersectSortedArrays(int[] a, int[] b){
    int[] c = new int[Math.min(a.length, b.length)]; 
    int ai = 0, bi = 0, ci = 0;
    while (ai < a.length && bi < b.length) {
        if (a[ai] < b[bi]) {
            ai++;
        } else if (a[ai] > b[bi]) {
            bi++;
        } else {
            if (ci == 0 || a[ai] != c[ci - 1]) {
                c[ci++] = a[ai];
            }
            ai++; bi++;
        }
    }
    return Arrays.copyOfRange(c, 0, ci); 
}

    Conceptuellement similaire à la vôtre, mais contient un certain nombre de simplifications.

    Je ne pense pas que vous pouvez améliorer à la fois la complexité.

    edit: j'ai essayé ce code, et il passe tous de vos tests unitaires.

  3. 3

    À l'aide de liste de tableaux pour stocker le résultat. 

    public ArrayList<Integer> arrayIntersection(int [] a, int[] b)
{
    int len_a=a.length;
    int len_b=b.length;
    int i=0;
    int j=0;
    ArrayList<Integer> alist=new ArrayList();

    while(i<len_a && j<len_b)
    {
        if(a[i]<b[j])
            i++;
        else if(a[i]>b[j])
            j++;
        else if(a[i]==b[j])
        {
            alist.add(a[i]);
            i++;
            j++;

        }
    }

   return alist;    
  }
  4. 0

    Si vous utilisez le 'Integer' (objet) des tableaux et souhaitez utiliser l'API java méthodes, vous pouvez vérifier le code ci-dessous. Notez que le code ci-dessous a probablement plus de complexité (car il utilise une logique de conversion d'un discbased à d'autres) et la consommation de mémoire (en raison de l'utilisation d'objets) que la méthode primitive, comme indiqué ci-dessus. Je l'ai juste essayé (hausse les épaules):

    public class MergeCollections {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        Set<Integer> intSet1 = new TreeSet<Integer>();
        intSet1.addAll(Arrays.asList(intArray1));
        intSet1.addAll(Arrays.asList(intArray2));
        System.out.println(intSet1);
    }
}

    Et la sortie:

    [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]

    Aussi, suivez ce lien: Algolist - Algo pour fusionner des tableaux triés

    MODIFIER: modification de la HashSet à TreeSet

    EDIT 2: Maintenant que la question est édité et clair, je suis en ajoutant une solution simple pour trouver intersection :

    public class Intersection {
    public static void main(String[] args) {
        Integer[] intArray1 = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        Integer[] intArray2 = new Integer[] {2, 3, 5, 7, 8, 11, 13};

        List<Integer> list1 = Arrays.asList(intArray1);
        Set<Integer> commonSet = new TreeSet<Integer>();
        for(Integer i: intArray2) {
            if(list1.contains(i)) {
                commonSet.add(i);
            }
        }

        System.out.println(commonSet);
    }
}
  5. 0

    Je ne sais pas si c'est une bonne idée pour résoudre le problème de cette façon:

    dire 

      A,B are 1 based arrays
    A.length=m
    B.length=n

    1) initialisation d'un tableau, C, min(m,n) de longueur

    2) se concentrer uniquement sur la partie commune en cochant la première et la dernière
    de l'élément. ici binaires de recherche pourrait être utilisé. prenons un exemple, pour enregistrer
    quelques mots: 

     A[11,13,15,18,20,28,29,80,90,100.........300,400]
    ^                                          ^
 B[3,4,5,6,7.8.9.10.12,14,16,18,20,..400.....9999]
                     ^                ^


then we need only focus  on

    A[start=1](11)-A[end=m](400)
    and
    B[start=9](12)-B[end](400)

    3). comparer les gamme (end-start) des deux Tableaux. en prenant le tableau avec les petits gamme , disons, pour chaque élément A[i] de A[start] ~ A[end]faire une recherche binaire dans B[start,end]

    • si trouvé, mettez l'élément en C, réinitialiser B. commencer à foundIdx+1,

    • sinon B. de démarrage est réglé sur le plus petit élément de [j], B[j] est
      plus qu'Un[i], de réduire la gamme

    4) continuez à 3) jusqu'à ce que tous les éléments dans Un[début, fin] a été traitée.

    • par l'étape 1, on peut trouver le cas si il n'y a pas d'intersection entre
      deux Tableau.
    • lorsque vous faites une recherche binaire dans l'étape 3, nous comparons[i], [i-1], si
      de même, passer d'Un[i]. afin de garder les éléments de C sont uniques.

    de cette façon, le pire ce serait le cas de lg(n!) si A et B sont de même) ? pas sûr.

    Avg cas?

  6. 0

    Ici un souvenir d'amélioration:

    Il serait préférable de les stocker vos résultats (C) dans une structure dynamique, comme une liste chaînée, et créer un tableau après vous avez terminé trouver l'intersection des éléments (exactement comme vous le faites avec de la matrice de r). Cette technique serait particulièrement utile si vous avez de très grands tableaux pour A et B et attendre les éléments communs d'être peu nombreux en comparaison (pourquoi rechercher un énorme bloc de mémoire contiguë quand vous avez seulement besoin d'une petite quantité?).

    EDIT: encore une chose que je voudrais changer, et cela peut être juste un peu tatillon, c'est que je voudrais éviter d'utiliser indépendant des boucles lorsque le pire des cas, le nombre d'itérations est connu avant de la main.