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

Question

我有2个列表，一个列表元素类型是结构A，另一个列表元素类型是结构B，结构A和结构B之间有公共字段。如何获取在 2 个列表之间具有相同内容的交集元素，并使用 golang 避免 o（n^2） 时间复杂度。string namenametype structA struct {   name string   ....}type structB struct {   name string   ..}注意：每个列表中的字段不是唯一的，因此转换地图的方式不是解决方案name

Answer 1

拥有不唯一的列表并不妨碍您使用地图;您可以执行如下操作（游乐场）：

package main

import (

    "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 bList

itersections := make([]*structB, 0, len(aList))

for k,v := range aMap {

    if b, ok := bMap[k];ok {

        itersections = append(intersections, b...)

    }

}