Golang如何快速获取两个不同结构体列表按公共name字段的交集且规避O(n²)复杂度

实现思路 #

• 为了适配name字段重复的场景，我们不做单值映射，而是按name分组存储同名称的所有元素
• 优先选择长度更短的列表构建分组映射，进一步降低内存占用和前期遍历开销
• 整体时间复杂度为O(m + n)，完全规避双重循环的O(n²)开销，其中m和n分别是两个列表的长度

代码实现 #

首先是题目给出的结构体定义：

type structA struct {
	name string
	// 其余字段省略
}

type structB struct {
	name string
	// 其余字段省略
}

交集获取函数实现：

// GetIntersection 按name字段取两个列表的交集
// 返回值1：所有匹配的元素对，[0]为structA实例，[1]为structB实例
// 返回值2：所有匹配到的structA元素列表（允许重复，符合name重复场景）
// 返回值3：所有匹配到的structB元素列表（允许重复，符合name重复场景）
func GetIntersection(listA []structA, listB []structB) ([][2]interface{}, []structA, []structB) {
	// 短列表优先构建映射，降低内存消耗
	if len(listA) > len(listB) {
		pairs, resB, resA := GetIntersection(listB, listA)
		// 反转配对顺序保证返回顺序符合入参顺序
		for i := range pairs {
			pairs[i][0], pairs[i][1] = pairs[i][1], pairs[i][0]
		}
		return pairs, resA, resB
	}

	// 构建name到structA列表的分组映射
	nameGroup := make(map[string][]structA, len(listA))
	for _, itemA := range listA {
		nameGroup[itemA.name] = append(nameGroup[itemA.name], itemA)
	}

	var (
		matchPairs [][2]interface{}
		matchListA []structA
		matchListB []structB
	)

	// 遍历长列表匹配映射
	for _, itemB := range listB {
		itemsA, exists := nameGroup[itemB.name]
		if !exists {
			continue
		}
		// 存储所有同name的匹配组合
		for _, a := range itemsA {
			matchPairs = append(matchPairs, [2]interface{}{a, itemB})
			matchListA = append(matchListA, a)
		}
		matchListB = append(matchListB, itemB)
	}
	return matchPairs, matchListA, matchListB
}

可选优化 #

如果不需要保留重复元素，只需要去重后的交集，可以额外引入标识位去重，避免相同元素被多次加入结果集。

内容的提问来源于stack exchange，提问作者Frank