/ / Subset-Check mit Slices in Go - Arrays, Go, Subset, Slice

Subset-Check mit Slices in Go - Arrays, Go, Subset, Slice

Ich bin auf der Suche nach einem effizienten Weg, um zu überprüfen, ob eine Scheibe eine Teilmenge einer anderen ist. Ich könnte einfach über sie iterieren, um zu überprüfen, aber ich denke, dass es einen besseren Weg geben muss.

Z.B.

{1, 2, 3} ist eine Teilmenge von {1, 2, 3, 4}
{1, 2, 2} ist KEINE Untermenge von {1, 2, 3, 4}

Was ist der beste Weg, dies effizient zu tun?

Vielen Dank!

Antworten:

4 für die Antwort № 1

Ich denke, der häufigste Weg, um ein Teilproblem zu lösen, ist über eine Karte.

package main

import "fmt"

// subset returns true if the first array is completely
// contained in the second array. There must be at least
// the same number of duplicate values in second as there
// are in first.
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}))
fmt.Println(subset([]int{1, 2, 2}, []int{1, 2, 3, 4}))
}

Die Möglichkeit, doppelte Werte zu überprüfen, ist relativ unüblich. Der obige Code löst das Problem wie gewünscht (siehe: http://play.golang.org/p/4_7Oh-fgDQ) obwohl. Wenn Sie beabsichtigen, doppelte Werte zu haben, müssen Sie eine Zählung wie im obigen Code beibehalten. Wenn es keine doppelten Werte gibt, können Sie das Problem kompakter lösen, indem Sie einen booleschen Wert für den Map-Wert anstelle einer Ganzzahl verwenden.


0 für die Antwort № 2

Wenn Ihre Scheiben sortiert sind, erledigt dies die Aufgabe.

package main

import "fmt"

// Subset return whether a is a sublist of b. Both a and b must be (weakly) ascending.
func Subset(a, b []int) bool {
for len(a) > 0 {
switch {
case len(b) == 0:
return false
case a[0] == b[0]:
a = a[1:]
b = b[1:]
case a[0] < b[0]:
return false
case a[0] > b[0]:
b = b[1:]
}
}
return true
}

func main() {
cases := []struct {
a, b []int
want bool
}{
{[]int{1, 2, 3}, []int{1, 2, 3, 4}, true},
{[]int{1, 2, 2}, []int{1, 2, 3, 4}, false},
}
for _, c := range cases {
if Subset(c.a, c.b) != c.want {
fmt.Printf("Subset(%v, %v) = %v, want %vn", c.a, c.b, Subset(c.a, c.b), c.want)
}
}
}