Ich war in verschiedenen Situationen oft mit diesem Problem konfrontiert. Es ist generisch für alle Programmiersprachen, obwohl ich mit C oder Java vertraut bin.

Betrachten wir zwei Arrays (oder Sammlungen):

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

Wie erhalte ich die gemeinsamen Elemente zwischen den beiden Arrays als neues Array? In diesem Fall ist der Schnittpunkt der Arrays A und B char[] c = {'c', 'd'}.

Ich möchte die wiederholte Iteration eines Arrays innerhalb des anderen Arrays vermeiden, die die Ausführungszeit um (Länge von A mal Länge von B) erhöht, was bei großen Arrays zu viel ist.

Gibt es eine Möglichkeit, einen einzelnen Durchgang in jedem Array durchzuführen, um die gemeinsamen Elemente zu erhalten?

Da dies für mich wie ein String-Algorithmus aussieht, gehe ich für einen Moment davon aus, dass es nicht möglich ist, diese Sequenz (daher String) zu sortieren. Dann können Sie den Longest Common Sequence-Algorithmus (LCS) verwenden.

Unter der Annahme, dass die Eingabegröße konstant ist, hat das Problem eine Komplexität von O (nxm) (Länge der beiden Eingaben).

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

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

Dieser Algorithmus ist O(N)zeitlich und O(N)räumlich.

Um zusätzlichen Platz zu vermeiden, können Sie den sortierungsbasierten Ansatz verwenden.

Die Untergrenze für die Effizienz ist O (n) - Sie müssen mindestens alle Elemente lesen. Dann gibt es mehrere Ansätze:

Dummester einfachster Ansatz

Suchen Sie nach jedem Element aus Array eins in Array zwei. Zeitkomplexität O (n ^ 2).

Sortieransatz

Sie müssen nur Array eins sortieren und dann mithilfe der binären Suche nach Elementen aus Array zwei suchen. Zeitliche Komplexität: Sortieren von O (nlogn), Suchen von O (n * logn) = O (nlogn), Gesamt-O (nlogn).

Hash-Ansatz

Erstellen Sie eine Hash-Tabelle aus Array-One-Elementen. Suchen Sie nach Elementen aus der zweiten Tabelle in der Hash-Tabelle. Die zeitliche Komplexität hängt von der Hash-Funktion ab. Sie können O (1) für Suchvorgänge im optimalen Fall erreichen (alle Elemente haben unterschiedliche Hashwerte), im schlimmsten Fall jedoch O (n) (alle Elemente haben denselben Hashwert). Gesamtzeitkomplexität: O (n ^ x), wobei x ein Faktor für die Effizienz der Hash-Funktion ist (zwischen 1 und 2).

Bei einigen Hash-Funktionen wird garantiert, dass eine Tabelle ohne Kollisionen erstellt wird. Das Gebäude benötigt jedoch nicht mehr für jedes Element streng O (1) Zeit. In den meisten Fällen ist es O (1). Wenn die Tabelle jedoch voll ist oder eine Kollision auftritt, muss die Tabelle erneut aufbereitet werden, wobei O (n) Zeit benötigt wird. Dies passiert nicht so oft, viel seltener als saubere Adds. Die AMORTISIERTE Zeitkomplexität ist also O (1). Es ist uns egal, dass einige der Adds O (n) Zeit benötigen, solange die Mehrheit der Adds O (1) Zeit benötigt.

Trotzdem muss die Tabelle im Extremfall bei jeder einzelnen Einfügung erneut aufgewärmt werden, sodass die strenge zeitliche Komplexität O (n ^ 2) wäre.

In einigen Sprachen gibt es einige Methoden, von denen ich weiß, dass sie genau das tun, was Sie wollen. Haben Sie sich überlegt, einige dieser Implementierungen zu betrachten?

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

Es gibt bereits viele gute Antworten darauf, aber wenn Sie den Einzeiler-Ansatz mit einer Bibliothek für Lazy-Coding verwenden möchten, würde ich mich für Google Guava (für Java) und seine Sets.intersectionMethode entscheiden.

^{(kein Compiler zur Hand, ertrage es mit mir)}

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))
);

Dies setzt natürlich voraus, dass beide Arrays keine Duplikate haben. In diesem Fall wäre die Verwendung einer festgelegten Datenstruktur sinnvoller und würde diese Art von Operation effizienter ermöglichen, insbesondere wenn Sie nicht von Anfang an von einem Array von Grundelementen ausgehen .

Kann oder kann nicht zu Ihrem Anwendungsfall passen, aber eine Art Kinderspiel für den allgemeinen Fall.

1. Sortieren Sie beide Arrays.
2. Führen Sie dann eine Schleife durch, bis sie gemeinsame Elemente haben. Oder eines der Arrays erreicht sein Ende.

Asymptotisch erfordert dies die Komplexität der Sortierung. dh O (NlogN) wobei N die Länge eines längeren Eingabearrays ist.

Wenn Sie sich für Duplikate interessieren, verwenden Sie eine Hash-Map, um Liste A zu indizieren, wobei der Schlüssel das Element und der Wert die Anzahl der Male ist, die dieses Element gesehen wurde.

Sie durchlaufen das erste und für jedes Element in A und fügen es dort mit dem Wert 1 ein. Wenn es bereits in der Karte vorhanden ist, fügen Sie diesem Wert eins hinzu.

Als nächstes iterieren Sie durch B, und wenn der Wert vorhanden ist, subtrahieren Sie 1. Wenn nicht, geben Sie -1 in den Wert in der Tabelle für dieses Element ein.

Zum Schluss durchlaufen Sie die Karte und drucken für jedes Element mit dem Wert! = 0 als Differenz aus.

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;
}

Dies sollte ausgeführt werden O(n), da wir die Listen jeweils nur einmal und die Karte nur einmal wiederholen. Die hier in Java verwendeten Datenstrukturen sollten effizient sein, da sie HashMapmit einer Kapazität aufgebaut sind, die die größte Größe der Listen verarbeiten kann.

Ich verwende a LinkedListfür die Rückgabe, da es uns die Möglichkeit bietet, eine Liste für unsere Kreuzung unbekannter Größe hinzuzufügen und zu durchlaufen.

Der beste Weg ist, überhaupt nicht mit Arrays zu beginnen. Arrays sind optimal für den wahlfreien Zugriff auf Elemente, aber nicht optimal für die Suche (darum geht es beim Finden der Kreuzung). Wenn Sie über Schnittmengen sprechen , müssen Sie die Arrays als Mengen betrachten. Verwenden Sie daher eine geeignetere Datenstruktur (in Java a Set). Dann ist die Aufgabe viel effizienter.

Sie können einen Baum verwenden, aber die Zeit ist O (n (log n)) und die Elemente müssen vergleichbar sein

Sortieren Sie zunächst die beiden Arrays mit dem besten Sortieralgorithmus.
Mit der linearen Suche können Sie dann die gemeinsamen Elemente erhalten.

Wenn ein zusätzlicher Speicherplatz bereitgestellt wird, können wir dazu die Hash-Tabelle verwenden.

in rubin kann man einfach sagen

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

c enthält ['c', 'd']

Sortieren Sie zuerst zwei Arrays und iterieren Sie sie dann. Wenn sie dasselbe Element sind, fügen Sie sie hinzu, um das Array zurückzugeben.

Code ist hier:

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));
}

Ausgänge:

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

Angenommen, Sie haben es mit ANSI-Zeichen zu tun. Der Ansatz sollte für Unicode ähnlich sein, ändern Sie einfach den Bereich.

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]]++;
}

Durchlaufen Sie nun das B, und Sie können überprüfen, ob der entsprechende Zeichensatzwert für das zu iterierende Zeichen größer als 0 ist. Sie können sie in einer Liste oder einer anderen Sammlung speichern.

Dieser Ansatz berücksichtigt die Komplexität der O (n) -Zeit und einen konstanten Platz für Ihre Überprüfungen, wobei Ihr neues Array / Ihre neue Liste, die zum Speichern der gemeinsamen Elemente verwendet wird, nicht berücksichtigt wird.

Dies ist in Bezug auf die Raumkomplexität besser als der HashSet / Hashtable-Ansatz.

Sie können HashSet in .NET 3.5 oder höher verwenden. Beispiel 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+ " ");

// Ausgabe: 8 15

Sortieren Sie jetzt eines der Arrays (m Log (m)). Wählen Sie jedes Element aus einem anderen Array aus und führen Sie eine binäre Suche im ersten Array (dem sortierten) durch -> n Log (m)

Gesamtzeitkomplexität: - (n + m) Protokoll (m) .

Ich hoffe, dass das Folgende nützlich wäre. Dies sind zwei verschiedene Ansätze:

• Einfacher Schnittpunkt, an dem Sie alle Elemente eines Arrays mit einem anderen Array vergleichen.

• Sortier- und suchbasierter Ansatz, bei dem ein Array sortiert und das zweite Array-Element im ersten Array mithilfe der binären Suche durchsucht wird.

//

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");
    }
}

Wenn die Sammlungen bereits sortiert sind, wie in der Frage gezeigt, ist die beste Lösung (noch nicht erwähnt) ein Algorithmus, der wie eine Zusammenführung sortiert ist und in O (n + m) ausgeführt wird.

Vergleichen Sie die ersten Elemente jeder Sammlung. Wenn sie identisch sind, fügen Sie das Element zur Schnittmenge hinzu und fügen Sie beide Elemente aus ihren Sammlungen hinzu. Wenn die Elemente unterschiedlich sind, fügen Sie das Element hinzu, das im Vergleich zum anderen Element größer ist. Wiederholen, bis eine Sammlung leer ist.

Unter Verwendung von Java 8-Funktionen ist hier ein Algorithmus, der Duplikate innerhalb einer Liste berücksichtigt, anstatt eine Liste in eine Menge umzuwandeln. Keine Sortierung, also nein n log n.

1. Konvertieren Sie eine der Listen in eine Karte, wobei der Wert die Anzahl der Vorkommen ist (Kosten: O (n)).
2. Wenn für jedes Element in der anderen Liste das Element in der Karte vorhanden ist, verringern Sie das Auftreten um eins (Kosten: O (n)).

Daher betragen die Gesamtkosten 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);
  }
}

Der obige Code gibt diese Ausgabe aus : [5, 3, 9, 9].

import 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]);
  }

  }
}