Intersection of Two Arrays

Q: Wie hoch ist die Zeitkomplexität der Schnittmenge zweier Arrays?

Mit einer Hash-Menge dauert es im Durchschnitt O(n + m) , die gemeinsamen Werte zu finden, und das Sortieren der k Werte der Antwort fügt O(k log k) hinzu; die Menge benötigt O(n) Speicherplatz. Beide Arrays zu sortieren und sie mit zwei Zeigern zu durchlaufen, dauert O(n log n + m log m) . Jedes Paar zu vergleichen, dauert O(n × m) .

LeichtHashing

+10

Du erhältst zwei Arrays aus Ganzzahlen, nums1 und nums2. Gib jeden Wert zurück, der in beiden Arrays vorkommt, sortiert in aufsteigender Reihenfolge. Jeder gemeinsame Wert erscheint in der Antwort einmal, unabhängig davon, wie oft er in einem der beiden Arrays vorkommt.

Funktion

intersection(nums1: integer-array, nums2: integer-array) → integer-array

nums1integer-array: die erste Liste von Ganzzahlen
nums2integer-array: die zweite Liste von Ganzzahlen
Gibt zurückinteger-array: die Werte, die in beiden Listen vorkommen, jeweils einmal und in aufsteigender Reihenfolge

Einschränkungen

1 ≤ nums1.length, nums2.length ≤ 5000
-10⁵ ≤ nums1[i], nums2[i] ≤ 10⁵
Mindestens ein Wert kommt in beiden Arrays vor.

Beispiele

Eingabe: nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
Ausgabe: [4, 6]
Erklärung: 4 und 6 kommen in beiden Arrays vor. 4 erscheint zweimal in nums2, wird aber nur einmal aufgeführt, und 2 und 9 kommen nie in nums2 vor.

Eingabe: nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
Ausgabe: [-3, 7]
Erklärung: -3 und 7 sind in beiden Arrays enthalten. In aufsteigender Reihenfolge kommt -3 zuerst, obwohl 7 in nums2 zuerst kommt.

+16 versteckte Tests beim Einreichen

Weiterführende Frage

Was wäre, wenn nums1 10 Werte und nums2 eine Million bereits sortierte Werte enthält? Für welchen Ansatz würdest du dich entscheiden, und kann die binäre Suche einen vollständigen Durchlauf übertreffen?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Zwei Details entscheiden bei diesem Problem: Ein Wert, der auf beiden Seiten vorkommt, kommt nur einmal in die Antwort, und die Antwort muss sortiert sein. Jedes Paar zu vergleichen funktioniert, kostet aber n × m Vergleiche, also 2.5 × 10^7, wenn beide Arrays 5000 Werte enthalten. Wenn du beide Arrays sortierst, können zwei Zeiger die gemeinsamen Werte der Reihe nach finden, und ein Hash-Set für eines der Arrays beantwortet „kommt dieser Wert in nums1 vor?“ in konstanter Zeit.

Vergleiche jedes Paar

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Gehe jeden Wert von nums1 durch und durchsuche nums2 nach ihm. Beende die Suche beim ersten Treffer und überspringe einen Wert, der bereits in der Antwort enthalten ist. So ergibt [8, 8, 8, 8] im Vergleich mit [8, 8] eine einzelne 8, nicht vier. Sortiere die Antwort am Ende.

Das ist korrekt, weil ein Wert genau dann in die Antwort kommt, wenn irgendein Vorkommen davon in nums1 einen Treffer in nums2 findet, und durch das Überspringen kommt er nicht zweimal hinein.

Das ist langsam, weil jeder Wert von nums1 möglicherweise ganz nums2 durchsuchen muss. Bei 5000 Werten in jedem Array sind das bis zu 2.5 × 10^7 Vergleiche, und bei den großen Tests findet der Großteil der Werte keinen Treffer, sodass die meisten Suchen bis zum Ende laufen.

Algorithmus

Beginne mit einer leeren Antwortliste.
Überspringe jeden Wert a in nums1, wenn er bereits in der Antwort enthalten ist.
Durchsuche andernfalls nums2; füge beim ersten Wert, der gleich a ist, a zur Antwort hinzu und beende die Suche.
Sortiere die Antwort in aufsteigender Reihenfolge und gib sie zurück.

def intersection(nums1, nums2):
    result = []
    for a in nums1:
        if a in result:
            continue
        # Look for a anywhere in nums2.
        for b in nums2:
            if a == b:
                result.append(a)
                break
    result.sort()
    return result

Sortiere beide, gehe dann mit zwei Zeigern durch

Idee

Sortiert ergibt Beispiel 1 [2, 2, 4, 6, 9] und [1, 4, 4, 6]. Setze den Zeiger i an den Anfang des ersten Arrays und j an den Anfang des zweiten. Der Zeiger auf dem kleineren Wert rückt vor: Dieser Wert kann mit keinem weiter hinten im anderen Array übereinstimmen, denn dort ist jeder Wert mindestens genauso groß. Sehen beide Zeiger denselben Wert, ist er beiden gemeinsam. Füge ihn also hinzu und bewege beide Zeiger.

Im Beispiel: 2 > 1 bewegt j, beide 2 sind kleiner als 4 und bewegen i, 4 = 4 fügt 4 hinzu, die zweite 4 ist kleiner als 6 und bewegt j, und 6 = 6 fügt 6 hinzu. Ein Wert, der auf beiden Seiten mehrmals vorkommt, etwa 2 in [2, 2, 3] und [2, 2], wird mehr als einmal zugeordnet; wenn du ihn mit dem zuletzt hinzugefügten Wert vergleichst, bleibt eine Kopie übrig. Das Ergebnis ist sortiert, ohne dass ein zusätzlicher Schritt nötig ist.

Das Sortieren kostet O(n log n + m log m), und der Durchlauf benötigt O(n + m), da jeder Schritt mindestens einen Zeiger bewegt. Die meisten Versionen sortieren Kopien, was O(n + m) Speicher benötigt. Wenn du die Eingaben umordnen darfst, sortiere sie direkt, wie es der C-Code macht; dann ist das Ergebnis der einzige zusätzliche Speicherbedarf.

Algorithmus

Sortiere beide Arrays.
Setze i = 0 und j = 0.
Solange sich beide Zeiger innerhalb ihrer Arrays befinden, bewege den Zeiger beim kleineren Wert.
Bei gleichen Werten füge den Wert hinzu, sofern er nicht dem zuletzt hinzugefügten Wert entspricht, und bewege dann beide Zeiger.
Gib die Antwort zurück.

def intersection(nums1, nums2):
    a = sorted(nums1)
    b = sorted(nums2)
    i, j = 0, 0
    result = []
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            i += 1
        elif a[i] > b[j]:
            j += 1
        else:
            # A shared value: keep it once, even if it repeats.
            if not result or result[-1] != a[i]:
                result.append(a[i])
            i += 1
            j += 1
    return result

Hash-Menge des ersten Arrays

Idee

Füge jeden Wert von nums1 in eine Hash-Menge ein. In Beispiel 1 ist die Menge {6, 2, 9, 4}: Die wiederholte 2 wird beim Einfügen zusammengefasst. Durchlaufe dann nums2 und frage die Menge für jeden Wert in konstanter Zeit ab. Die erste 4 ist enthalten und kommt daher in die Antwort. Die zweite 4 darf nicht hineinkommen, also entfernst du einen Wert aus der Menge, sobald er übereinstimmt. 1 ist nicht enthalten und 6 ist enthalten; so erhältst du [4, 6].

Das Entfernen bei einer Übereinstimmung sorgt dafür, dass jeder Wert nur einmal vorkommt: Nach seiner ersten Übereinstimmung ist ein Wert aus der Menge verschwunden, sodass spätere Kopien in nums2 nichts mehr finden. Jeder hinzugefügte Wert ist in beiden Arrays enthalten, und jeder gemeinsame Wert wird hinzugefügt, sobald seine erste Kopie in nums2 eintrifft.

Das Erstellen der Menge und das Durchlaufen benötigen im Durchschnitt O(n + m). Die Antwort wird in der Reihenfolge von nums2 ausgegeben, also sortiere sie am Ende; sie enthält k ≤ min(n, m) Werte, was O(k log k) kostet. C hat keine eingebaute Menge, daher verwendet der C-Code ein Markierungsarray, dessen Index value + 10^5 ist; das funktioniert, weil die Werte begrenzt sind.

Algorithmus

Erstelle eine Hash-Menge first aus nums1.
Füge für jeden Wert in nums2, der in first enthalten ist, diesen zur Antwort hinzu und entferne ihn aus first.
Sortiere die Antwort in aufsteigender Reihenfolge.
Gib sie zurück.

def intersection(nums1, nums2):
    first = set(nums1)
    result = []
    for num in nums2:
        if num in first:
            result.append(num)
            # Remove it so a repeat in nums2 is not added twice.
            first.remove(num)
    result.sort()
    return result

Stolperfallen und Grenzfälle

Die meisten falschen Antworten entstehen hier durch wiederholte Werte und durch die Reihenfolge der Ausgabe.

Bei jedem Treffer einen Wert hinzufügen. [2, 2, 3, 3, 3] und [3, 2, 2] haben zwei Werte gemeinsam, also lautet die Antwort [2, 3] und nicht [3, 2, 2].
Die Werte in der Reihenfolge zurückgeben, in der du sie gefunden hast. Der Durchlauf durch die Hash-Menge folgt nums2, daher muss [7, -3] trotzdem zu [-3, 7] sortiert werden.
Zahlen als Text sortieren. JavaScripts sort() vergleicht ohne Vergleichsfunktion Zeichenfolgen, daher bleibt [100000, 99] in dieser Reihenfolge. Übergib (x, y) => x - y.
Eine Schnittmenge von Mengen verwenden und die Reihenfolge vergessen. Pythons set(nums1) & set(nums2) findet die richtigen Werte in keiner bestimmten Reihenfolge; umschließe den Ausdruck mit sorted.
Ein Flag-Array mit dem Rohwert als Index verwenden. -3 ist kein gültiger Index; verschiebe zuerst jeden Wert um 10^5.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität der Schnittmenge zweier Arrays?

Mit einer Hash-Menge dauert es im Durchschnitt O(n + m), die gemeinsamen Werte zu finden, und das Sortieren der k Werte der Antwort fügt O(k log k) hinzu; die Menge benötigt O(n) Speicherplatz. Beide Arrays zu sortieren und sie mit zwei Zeigern zu durchlaufen, dauert O(n log n + m log m). Jedes Paar zu vergleichen, dauert O(n × m).

Solltest du eine Hash-Menge oder zwei Zeiger verwenden?

Verwende die Hash-Menge, wenn die Arrays unsortiert sind und genügend Speicher verfügbar ist: Sie erfordert den geringsten Aufwand. Verwende zwei Zeiger, wenn beide Arrays bereits sortiert vorliegen oder der Speicher knapp ist und du sie direkt sortieren kannst. Der Durchlauf benötigt keine Menge und liefert das Ergebnis in der richtigen Reihenfolge.

Wie behältst du wiederholte Werte in der Schnittmenge?

Wenn ein Wert so oft vorkommen soll, wie er in beiden Arrays vorkommt, sodass [3, 1, 3, 3] und [3, 3] [3, 3] ergeben, ersetze die Menge durch eine Zähl-Map. Zähle die Werte von nums1 und füge für jeden Wert von nums2, dessen Anzahl größer als null ist, diesen hinzu und verringere seine Anzahl. Entferne beim Durchlauf mit zwei Zeigern die Prüfung gegen den zuletzt hinzugefügten Wert.

Wie findest du die Schnittmenge, wenn ein Array zu groß für den Speicher ist?

Erstelle die Hash-Menge aus dem Array, das hineinpasst, und lies das große Array stückweise ein. Prüfe jeden Wert gegen die Menge und entferne ihn bei einer Übereinstimmung. Der Speicherbedarf bleibt auf die Größe des kleineren Arrays beschränkt. Wenn keines der beiden Arrays hineinpasst, sortiere beide auf der Festplatte und führe den Zwei-Zeiger-Durchlauf über die sortierten Dateien aus.

Python

def intersection(nums1, nums2):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

nums1 = [6, 2, 9, 2, 4]
nums2 = [4, 4, 1, 6]

Erwartet

[4, 6]

Intersection of Two Arrays

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Vergleiche jedes Paar

Sortiere beide, gehe dann mit zwei Zeigern durch

Hash-Menge des ersten Arrays

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben