VB.NET Array Intersection

Question

Das könnte schrecklich trivial sein, aber ich habe Probleme, eine Antwort zu finden, die in weniger als 2 Mal ausgeführt wird. Nehmen wir an, ich habe zwei String-Arrays und möchte wissen, welche Strings in beiden Arrays existieren. Wie würde ich das tun, effizient, in VB.NET oder ist gibt es eine Möglichkeit, dies als eine doppelte Schleife zu tun?

Answer 1

Der einfache Weg (unter der Annahme, dass kein. NET 3.5) ist, die Zeichenfolgen aus einem Array in einer Hashtabelle auszugeben, und dann durch das andere Array durch die Hashtabelle zu überprüfen. Das sollte viel schneller sein als eine n^2 Suche.

Answer 2

Beide Listen sortieren. Dann können Sie mit Sicherheit wissen, dass, wenn der nächste Eintrag in Liste A "Kopfsteinpflaster" ist und der nächste Eintrag in Liste B "definitiv" ist, dann "Kopfsteinpflaster" nicht in Liste B ist. Bewegen Sie einfach den Zeiger/Zähler auf die Liste das untergeordnete Ergebnis und die Rangliste aufsteigen.

Zum Beispiel:

Liste 1: D, B, M, A, I
Liste 2: I, A, P, N, D, G

sortiert:

Liste 1: A, B, D, I, M
Liste 2: A, D, G, I, N, P

A gegen A -> Spiel, Speicher A, vorrücken sowohl
B vs D - -> B D vs D -> Übereinstimmung, s vorrücken tore D, die beide
I vs G -> I> G, vorzurücken 2
I vs I -> Spiel, Speicher I, vorzurücken beide
M vs N -> M Liste 1 hat keine weiteren Artikel , Verlassen.
Liste der Spiele ist A, D, I

2 Liste sortiert O (n log (n)) plus O (n) Vergleiche macht dies O (n (log (n) + 1)).

Answer 3

Wenn eines der Arrays sortiert Sie es in der inneren Schleife eine binäre Suche tun, das wird die Zeit O(n log n)

Answer 4

verringern Wenn Sie beide Felder sortieren, Sie dann durch sie jeder einmal gehen kann Finde alle passenden Strings.

Pseudo-Code:

while(index1 < list1.Length && index2 < list2.Length) 
{ 
    if(list1[index1] == list2[index2]) 
    { 
     // You've found a match 
     index1++; 
     index2++; 
    } else if(list1[index1] < list2[index2]) { 
     index1++; 
    } else { 
     index2++; 
    } 
} 

Dann haben Sie es zu der Zeit, reduziert es die Sortierung zu tun braucht.