Wie kann in Go effizient festgestellt werden, ob ein ganzzahliges Slice eine Teilmenge eines anderen ist?

Teilmengenprüfung mit ganzzahligen Slices in Go

Die effiziente Bestimmung, ob ein Slice eine Teilmenge eines anderen ist, ist ein häufiges Problem bei der Programmierung. Ohne einen geeigneten Ansatz kann die Iteration über jedes Element der Slices zum Vergleich zeitaufwändig sein.

Optimale Lösung: Kartenbasierter Ansatz

Eine effiziente Lösung für dieses Problem nutzt eine Kartendatenstruktur . So funktioniert es:

<code class="go">package main

import "fmt"

func subset(first, second []int) bool {
    set := make(map[int]int)
    for _, value := range second {
        set[value] += 1
    }

    for _, value := range first {
        if count, found := set[value]; !found {
            return false
        } else if count < 1 {
            return false
        } else {
            set[value] = count - 1
        }
    }

    return true
}

func main() {
    fmt.Println(subset([]int{1, 2, 3}, []int{1, 2, 3, 4})) // true
    fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4})) // false
}</code>

Bei diesem Ansatz:

1. Wir erstellen eine Karte (einen Satz), um die Elemente des zweiten Slice zusammen mit ihrer Anzahl zu speichern.
2. Wir durchlaufen das erste Segment und prüfen, ob jedes Element in der Karte vorhanden ist. Wenn ein Element nicht gefunden wird, sind die Slices keine Teilmenge.
3. Wenn ein Element gefunden wird, verringern wir seine Anzahl in der Karte. Wenn die Anzahl Null wird, wissen wir, dass wir alle Instanzen dieses Elements gefunden haben.
4. Wenn alle Prüfungen erfolgreich sind, geben wir „true“ zurück, was anzeigt, dass das erste Segment eine Teilmenge des zweiten ist.

Umgang mit doppelten Werten

Die obige Lösung behandelt auch doppelte Werte effektiv. Beispielsweise ist {1, 2, 2} keine Teilmenge von {1, 2, 3, 4}, da das zweite Segment nur eine 2 enthält. Der Code verfolgt die Zählungen in der Karte und stellt so sicher, dass das erste Segment kein Duplikat mehr aufweist Elemente als das zweite Slice.

Das obige ist der detaillierte Inhalt vonWie kann in Go effizient festgestellt werden, ob ein ganzzahliges Slice eine Teilmenge eines anderen ist?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!