如何更快地获得2个列表之间的交集

Question

我有2个列表，一个列表元素类型是结构A，另一个列表元素类型是结构B，结构A和结构B之间有公共字段。如何获取在 2 个列表之间具有相同内容的交集元素，并使用 golang 避免 o（n^2） 时间复杂度。string namename

type structA struct {

   name string

   ....

}

type structB struct {

   name string

   ..

}

注意：每个列表中的字段不是唯一的，因此转换地图的方式不是解决方案name

Answer 1

拥有不唯一的列表并不妨碍您使用地图;您可以执行如下操作（游乐场）：package mainimport (    "fmt")func main() {    type structA struct {        name       string        otherfield int    }    type structB struct {        name           string        differentField bool    }    aSlice := []structA{        {name: "foo", otherfield: 1},        {name: "foo", otherfield: 2},        {name: "unique", otherfield: 3},        {name: "one", otherfield: 4},    }    bSlice := []structB{        {name: "foo", differentField: true},        {name: "foo", differentField: false},        {name: "noIntersection", differentField: true},        {name: "one", differentField: false},    }    inA := make(map[string][]interface{})    for _, a := range aSlice {        inA[a.name] = append(inA[a.name], a)    }    intersect := make(map[string][]interface{})    for _, b := range bSlice {        if _, ok := intersect[b.name]; ok {            intersect[b.name] = append(intersect[b.name], b)            continue        }        if a, ok := inA[b.name]; ok {            intersect[b.name] = append(a, b)            continue        }    }    fmt.Println(intersect)}

Answer 2

我想你可以尝试在戈朗使用地图。平均复杂度时间是 O（n），因为 golang 中的映射基于哈希表。示例代码：aMap := make(map[string][]*structA)for _,a := range aList {    aMap[a.name] = append(aMap[a.name], a)}bMap := make(map[string][]*structB)for _,b := range bList {    bMap[b.name] = append(bMap[b.name], b)}//get an intersection of aList and bListitersections := make([]*structB, 0, len(aList))for k,v := range aMap {    if b, ok := bMap[k];ok {        itersections = append(intersections, b...)    }}