foreach element e in array A
    insert e into hash table H

foreach element e in array B
    if H contains e 
        print e

Cet algorithme est O(N) dans le temps et O(N) dans l'espace.

pour éviter l'espace supplémentaire, vous pouvez utiliser l'approche basée sur le tri.

la limite inférieure de l'efficacité est O(n) - vous devez au moins lire tous les éléments. Puis il y a plusieurs répartitions:

L'approche la plus simple et stupide

rechercher chaque élément du tableau un dans le tableau deux. Complexité temporelle O(n^2).

méthode de tri

vous devez trier seulement le tableau un, puis rechercher des éléments du tableau deux en utilisant la recherche binaire. Complexité du temps: Tri O( nlogn), recherche O(n * logn) = O(nlogn), le total de O(nlogn).

Hachage approche

crée une table de hachage à partir des éléments du tableau un. La recherche des éléments forme la deuxième table dans la table de hachage. La complexité temporelle dépend de la fonction de hachage. Vous pouvez obtenir O (1) pour les recherches dans le cas optimal (tous les éléments auront une valeur de hachage différente), mais O(n) dans le pire des cas (tous les éléments auront la même valeur de hachage). Complexité totale du temps: O (N^x), où x est un facteur de hachage efficacité fonctionnelle (entre 1 et 2).

certaines fonctions de hachage sont garanties pour construire une table sans collisions. Mais le bâtiment ne prend plus strictement O (1) temps pour chaque élément. Il sera O(1) dans la plupart des cas, mais si la table est pleine ou si une collision est rencontrée, alors la table doit être reformulée - en prenant O (n) temps. Ce n'est pas si souvent, beaucoup moins fréquemment que nettoyer ajoute. Donc la complexité amortie du temps est O (1). Nous ne nous soucions pas de certains ads prendre du temps O(n), aussi longtemps que la majorité des adds prend du temps O (1).

mais même ainsi, dans un cas extrême, la table doit être rabâché chaque insertion simple, de sorte que la complexité de temps stricte serait O (N^2)

il y a quelques méthodes dans certaines langues que je connais qui font exactement ce que vous voulez, Avez-vous envisagé d'examiner certaines de ces implémentations?

PHP - array_intersect ()

$array1 = array("a" => "green", "red", "blue");
$array2 = array("b" => "green", "yellow", "red");
$result = array_intersect($array1, $array2);
print_r($result);

>> green
   red

Java - List.retainAll

Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));

listOne.retainAll( listTwo );
System.out.println( listOne );

>> dingo, hafil, iga

    public static void main(String[] args) {
        char[] a = {'a', 'b', 'c', 'd'};
        char[] b = {'c', 'd', 'e', 'f'};
        System.out.println(intersect(a, b));
    }

    private static Set<Character> intersect(char[] a, char[] b) {
        Set<Character> aSet = new HashSet<Character>();
        Set<Character> intersection = new HashSet<Character>();
        for (char c : a) {
            aSet.add(c);
        }
        for (char c : b) {
            if (aSet.contains(c)) {
                intersection.add(c);
            }
        }
        return intersection;
    }

int s[256] // for considering all ascii values, serves as a hash function

for(int i=0;i<256;i++)
s[i]=0;

char a[]={'a','b','c','d'};
char b[]={'c','d','e','f'};

for(int i=0;i<sizeof(a);i++)
{
   s[a[i]]++;
 }

 for(int i=0;i<sizeof(b);i++)//checker function
 {
     if(s[b[i]]>0)
       cout<<b[i]; 
  }


  complexity O(m+n);
  m- length of array a
  n- length of array b

Google Guava

il y a déjà beaucoup de bonnes réponses à cela, mais si vous voulez l'approche mono-liner en utilisant une bibliothèque pour le codage paresseux, je dirais Google Guava (pour Java) et sa méthode Sets.intersection .

^{(pas de compilateur sous la main, de garder avec moi)}

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};

Set<Character> intersection = Sets.intersection(
    Sets.newHashSet<Character>(Chars.asList(a)),
    Sets.newHashSet<Character>(Chars.asList(b))
);

évidemment, cela suppose que les deux tableaux ne seraient pas ont des doublons, auquel cas l'utilisation d'une structure de données établie serait plus logique et permettrait ce genre d'opération plus efficacement, surtout si vous ne commencez pas à partir d'un tableau de primitives dès le début.

peut ou ne peut pas correspondre à votre cas d'utilisation, mais en quelque sorte l'approche sans hésitation pour le cas général.

1. triez les deux tableaux.
2. font alors boucle jusqu'à ce qu'ils aient des éléments communs ou un des tableaux atteint son extrémité.

asymptotiquement, cela prend la complexité du tri. i.e. O (NlogN) où N est la longueur du tableau d'entrée le plus long.

si vous vous souciez des doublons, utilisez une carte de hachage pour indexer la liste A, avec la clé étant l'élément, et la valeur étant un certain nombre de fois que cet élément a été vu.

Vous parcourez la première et pour chaque élément de A, et si elle n'existe pas dans la map, mettre dans une valeur de 1, si elle existe déjà dans la map, ajouter un à cette valeur.

ensuite, itérez B, et si la valeur existe, soustrayez 1. Si non, mettre -1 dans la valeur sur le tableau pour cet élément.

enfin, itérez à travers la carte et pour tout élément ayant une valeur != 0, imprimer, une différence.

private static <T> List<T> intersectArrays(List<T> a, List<T> b) {
    Map<T, Long> intersectionCountMap = new HashMap<T, Long>((((Math.max(a.size(), b.size()))*4)/3)+1);
    List<T> returnList = new LinkedList<T>();
    for(T element : a) {
        Long count = intersectionCountMap.get(element);
        if (count != null) {
            intersectionCountMap.put(element, count+1);
        } else {
            intersectionCountMap.put(element, 1L);
        }
    }
    for (T element : b) {
        Long count = intersectionCountMap.get(element);
        if (count != null) {
            intersectionCountMap.put(element, count-1);
        } else {
            intersectionCountMap.put(element, -1L);
        }            
    }
    for(T key : intersectionCountMap.keySet()) {
        Long count = intersectionCountMap.get(key);
        if (count != null && count != 0) {
            for(long i = 0; i < count; i++) {
                returnList.add(key);
            }
        }
    }
    return returnList;
}

cela devrait s'exécuter dans O(n) , car nous n'itérons les listes qu'une fois, et la carte qu'une fois. Les structures de données utilisées ici en Java devraient être efficaces, car le HashMap est construit avec une capacité qui peut gérer la plus grande taille des listes.

j'utilise un LinkedList pour le retour car il nous fournit une façon d'ajouter et d'itérer à travers une liste pour notre intersection de taille inconnue.

La meilleure façon est de ne pas commencer avec des tableaux. Les tableaux sont optimaux pour l'accès aléatoire aux éléments, mais pas optimaux pour la recherche (qui est ce que trouver l'intersection est tout au sujet). Comme vous parlez de intersection , vous devez être concernant les tableaux comme ensembles. Utilisez donc une structure de données plus appropriée (en Java, un Set ). Ensuite, la tâche est beaucoup plus efficace.

vous pouvez utiliser l'arbre, mais le temps sera O(N (log n)) et les éléments doivent être comparables

d'abord, trier les deux tableaux en utilisant le meilleur algorithme de tri.

Puis, avec recherche linéaire, vous pouvez obtenir les éléments communs.

si un espace supplémentaire est prévu, nous pouvons utiliser la table de hachage pour le faire.

dans ruby vous pouvez juste dire

a = ['a', 'b', 'c', 'd']
b = ['c', 'd', 'e', 'f']
c = a & b

c contient ['c',' d']

Trier deux tableaux d'abord, puis les itérer, s'ils sont le même élément, Ajouter au tableau à retourner.

est ici:

public static void printArr(int[] arr){
    for (int a:arr){
        System.out.print(a + ", ");
    }
    System.out.println();
}

public static int[] intersectionOf(int[] arr1, int[] arr2){
    Arrays.sort(arr1);
    Arrays.sort(arr2);

    printArr(arr1);
    printArr(arr2);

    int i=0, j=0, k=0;
    int[] arr = new int[Math.min(arr1.length, arr2.length)];

    while( i < arr1.length && j < arr2.length){
        if(arr1[i] < arr2[j]){
            i++;
        } else if(arr1[i] > arr2[j]){
            j++;
        } else {
            arr[k++] = arr1[i++];
            j++;
        }
    }
    return Arrays.copyOf(arr, k);
}

public static void main(String[] args) {
    int[] arr1 = {1, 2, 6};
    int[] arr2 = {10, 2, 5, 1};
    printArr(intersectionOf(arr1,arr2));
}

sorties:

arr1: 1, 2, 6, 
arr2: 1, 2, 5, 10, 
arr: 1, 2, 

en supposant que vous avez affaire à des personnages ANSI. L'approche devrait être similaire pour Unicode, il suffit de changer la gamme.

char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
int[] charset = new int[256]

for(int i=0; i<A.length; i++) {
  charset[A[i]]++;
}

maintenant itérez sur le B et vous pouvez vérifier si la valeur du jeu de caractères correspondant pour le caractère itéré est supérieure à 0. Vous pouvez les stocker dans une liste ou toute autre collection.

cette approche prend en compte la complexité du temps et un espace constant pour vos vérifications tableau / liste servant à contenir les éléments communs.

c'est mieux que L'approche HashSet/Hashtable en termes de complexité spatiale.

vous pouvez utiliser le HashSet dans .NET 3.5 ou plus tard. Exemple C # code:

HashSet<int> set1 = new HashSet<int>(new int[]{8, 12, 13, 15});

HashSet<int> set2 = new HashSet<int>(new int[] { 15, 16, 7, 8, 9 });

set1.IntersectWith(set2);

foreach (int i in set1)

   Console.Write(i+ " ");

/ / sortie: 8 15

Trier un des tableaux (m Log(m) ) maintenant, choisissez chaque élément d'un autre tableau et faire une recherche binaire dans le premier tableau(triées) ->n Log(m)

Temps Total de la Complexité :- (n+m)Log(m) .

j'espère que ce qui suit serait utile. Ce sont deux approches différentes:

• simple Intersection où vous comparez tous les éléments d'un tableau à un autre tableau.

• de Tri et de recherche basée sur l'approche qui trie un tableau et de recherche deuxième élément de tableau en premier tableau à l'aide de binaire rechercher.

//

public class IntersectionOfUnsortedArrays {
    public static void main(String[] args) {
        int[] arr1 = { 12, 4, 17 };
        int[] arr2 = { 1, 12, 7, 17 };
        System.out.println("Intersection Using Simple Comparision");
        printArray(simpleIntersection(arr1, arr2));
        System.out.println("Intersection Using Sort and Binary Search");
        printArray(sortingBasedIntersection(arr1, arr2));
    }

    /*
     * Simple intersection based on the comparison without any sorting.
     * Complexity O(n^2)
     */
    public static int[] simpleIntersection(int[] a, int[] b) {
        int minlen = a.length > b.length ? b.length : a.length;
        int c[] = new int[minlen];
        int k=0;
        for(int i=0;i<a.length;i++){
            for(int j=0;j<b.length;j++){
                if(a[i]==b[j]){
                    c[k++]=a[i];
                }
            }
        }
        int arr[] = new int[k];
        // copy the final array to remove unwanted 0's from the array c
        System.arraycopy(c, 0, arr, 0, k);
        return arr;
    }

    /*
     * Sorting and Searching based intersection.
     * Complexity Sorting O(n^2) + Searching O(log n)
     */

    public static int[] sortingBasedIntersection(int[] a, int[] b){
        insertionSort(a);
        int minlen = a.length > b.length ? b.length : a.length;
        int c[] = new int[minlen];
        int k=0;
        for(int i=0;i<b.length;i++){
            int result = binarySearch(a,0,a.length,b[i]);
            if(result > -1){
                c[k++] = a[result];
            }
        }
        int arr[] = new int[k];
        // copy the final array to remove unwanted 0's from the array c
        System.arraycopy(c, 0, arr, 0, k);
        return arr;
    }

    public static void insertionSort(int array[]) {
        for (int i = 1; i < array.length; i++) {
            int j = i;
            int b = array[i];
            while ((j > 0) && (array[j - 1] > b)) {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = b;
        }
    }

    static int binarySearch(int arr[], int low, int high, int num) {
        if (high < low)
            return -1;
        int mid = (low + high) / 2;
        if (num == arr[mid])
            return mid;
        if (num > arr[mid])
            return binarySearch(arr, (mid + 1), high, num);
        else
            return binarySearch(arr, low, (mid - 1), num);
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(" "+value);
        }
        System.out.println("\n");
    }
}

si les collections sont déjà triées, comme indiqué dans la question, alors la meilleure solution (pas encore mentionnée) est un algorithme de type merge-sort qui s'exécute en O(n+m).

comparez les premiers éléments de chaque collection. S'ils sont les mêmes, ajoutez l'élément à l'ensemble d'intersection et pop deux éléments de leurs collections. Si les éléments sont différents, pop l'élément qui est plus grand, en comparaison, à l'autre élément. Répéter jusqu'à ce qu'une collection soit vide.

en utilisant les fonctionnalités de Java 8, Voici un algorithme qui honore les doublons dans une liste au lieu de transformer une liste en un ensemble. Pas de tri, donc pas de n log n .

1. Convertissez l'une des listes en une carte, la valeur étant le nombre d'occurrences (coût: O(n)).
2. pour chaque élément de l'autre liste, si l'élément existe dans la carte, diminuer la fréquence d'un (coût: O(n)).

par conséquent, le coût global est O (n). Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class Dup {
  public static void main(String[] args) {
    List<Integer> listA = Arrays.asList(3, 1, 4, 1, 9, 5, 9);
    List<Integer> listB = Arrays.asList(2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3);
    findCommons(listA, listB);
  }

  static void findCommons(List<Integer> listA, List<Integer> listB) {
    Map<Integer, Long> mapA = 
        listA.stream().collect(
            Collectors.groupingBy(Integer::intValue, Collectors.counting()));

    List<Integer> commons = new ArrayList<>();
    listB.stream()
        .filter(e -> mapA.get(e) != null)
        .filter(e -> mapA.get(e) > 0)
        .forEach(e -> {
            mapA.put(e, mapA.get(e) - 1);
            commons.add(e);
        });

    System.out.println(commons);
  }
}

Code ci-dessus donnera cette sortie: [5, 3, 9, 9] .

importer java.util.Scanner;

public class arraycommon {

public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    // display common element in two diffrent array
    int sizea,sizeb,i=0,j=0,k=0;
    int count=0;
    System.out.println("enter the size array A:"+'\n');
    sizea=sc.nextInt();
    System.out.println("enter the size array B"+'\n');
    sizeb=sc.nextInt();
    int a[]=new int[sizea];
    int b[]=new int[sizeb];
    int c[]=new int[sizea];


    System.out.println("enter the element in array A:"+'\n');
    for (i = 0; i < sizea; i++) {

        a[i]=sc.nextInt();
    }
    System.out.println("enter the element in array B:"+'\n');
    for (i = 0; i < sizeb; i++) {

        b[i]=sc.nextInt();
    }
    System.out.println("the element in array A:"+'\n');
    for (i = 0; i < sizea; i++) {

        System.out.print(a[i]+" ");

    }
    System.out.println('\n');
    System.out.println("the element in array B:"+'\n');
    for (i = 0; i < sizeb; i++) 
    {

        System.out.print(b[i]+" ");
    }

    for (i = 0; i <sizea; i++) 
    {
        for (j = 0; j < sizeb; j++) 
        {
           if(a[i]==b[j])
           {
               count++;
               c[k]=a[i];
               k=k+1;
           }
        }
    }
    System.out.println('\n');
    System.out.println("element common in array is");

    if(count==0)
    {
        System.out.println("sorry no common elements");
    }
    else
    {
        for (i = 0; i <count; i++) 
        {

        System.out.print(c[i]+" ");
        }
    }

}

}

    simply search each element of first array with each element of second array and stored matched result in third array
class Union
{
  public static void main(String[] args) {
  char a[] ={'f','g','d','v','a'};
  char b[] ={'a','b','c','d','e'};
  char temp[] = new char[5];
  int p=0;
  for(int i=0;i<a.length;i++)
  {
    for(int j=0;j<b.length;j++)
    {
      if(a[i]==b[j])     //searches if both array has common element
      {

        temp[p] = a[i];   //if match found store it in a new array
        p++;
      }

    }

  }
  for(int k=0;k<temp.length;k++)
  {
      System.out.println(temp[k]);
  }

  }
}