如何在golang中获得两个切片的交集？

Question

有没有有效的方法在Go中获得两个切片的交集？

我想避免嵌套for循环解决方案

slice1 := []string{"foo", "bar","hello"}
slice2 := []string{"foo", "bar"}

intersection(slice1, slice2)
=> ["foo", "bar"]

字符串的顺序无关紧要

Answer 1

如何将两个数组之间的交集作为新数组？

• 简单路口:中的每个元素进行比较A,以在各B(O(n^2))
• 哈希交集:将它们放入哈希表(O(n))
• 排序交叉点:排序A并执行优化交叉点(O(n*log(n)))

所有这些都在这里实施

https://github.com/juliangruber/go-intersect

Answer 2

简单、通用、多切片！（转到 1.18）

时间复杂度：可能是线性的

func interSection[T constraints.Ordered](pS ...[]T) []T {
    hash := make(map[T]*int) // value, counter
    result := make([]T, 0)
    for _, slice := range pS {
        duplicationHash := make(map[T]bool) // duplication checking for individual slice
        for _, value := range slice {
            if _, isDup := duplicationHash[value]; !isDup { // is not duplicated in slice
                if counter := hash[value]; counter != nil { // is found in hash counter map
                    if *counter++; *counter >= len(pS) { // is found in every slice
                        result = append(result, value)
                    }
                } else { // not found in hash counter map
                    i := 1
                    hash[value] = &i
                }
                duplicationHash[value] = true
            }
        }
    }
    return result
}
func main() {
    slice1 := []string{"foo", "bar", "hello"}
    slice2 := []string{"foo", "bar"}
    fmt.Println(interSection(slice1, slice2))
    // [foo bar]

    ints1 := []int{1, 2, 3, 9, 8}
    ints2 := []int{10, 4, 2, 4, 8, 9} // have duplicated values
    ints3 := []int{2, 4, 8, 1}
    fmt.Println(interSection(ints1, ints2, ints3))
    // [2 8]
}

游乐场：https://go.dev/play/p/lE79D0kOznZ

Answer 3

是的，有几种不同的方法可以解决这个问题。这是一个可以优化的示例。

package main

import "fmt"

func intersection(a []string, b []string) (inter []string) {
    // interacting on the smallest list first can potentailly be faster...but not by much, worse case is the same
    low, high := a, b
    if len(a) > len(b) {
        low = b
        high = a
    }

    done := false
    for i, l := range low {
        for j, h := range high {
            // get future index values
            f1 := i + 1
            f2 := j + 1
            if l == h {
                inter = append(inter, h)
                if f1 < len(low) && f2 < len(high) {
                    // if the future values aren't the same then that's the end of the intersection
                    if low[f1] != high[f2] {
                        done = true
                    }
                }
                // we don't want to interate on the entire list everytime, so remove the parts we already looped on will make it faster each pass
                high = high[:j+copy(high[j:], high[j+1:])]
                break
            }
        }
        // nothing in the future so we are done
        if done {
            break
        }
    }
    return
}

func main() {
    slice1 := []string{"foo", "bar", "hello", "bar"}
    slice2 := []string{"foo", "bar"}
    fmt.Printf("%+v\n", intersection(slice1, slice2))
}

现在，上面定义的交集方法将仅在slicesof上运行strings，就像您的示例一样。理论上，您可以创建一个如下所示的定义func intersection(a []interface, b []interface) (inter []interface)，但是您将依赖反射和类型转换以便进行比较，这会增加延迟和使你的代码更难阅读。为您关心的每种类型编写单独的函数可能更容易维护和阅读。

func intersectionString(a []string, b []string) (inter []string),

func intersectionInt(a []int, b []int) (inter []int),

func intersectionFloat64(a []Float64, b []Float64) (inter []Float64), ..等

一旦确定了要如何实现它，您就可以创建自己的包并重复使用。

package intersection

func String(a []string, b []string) (inter []string)

func Int(a []int, b []int) (inter []int)

func Float64(a []Float64, b []Float64) (inter []Float64)