时间戳

首页 > 解决方案 > 从两个切片的重复项创建一个切片

arrays - 从两个切片的重复项创建一个切片

问题描述

我有两片：

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}

预期结果：

[]string{"c", "d"}

使用此规范从重复项创建切片的最佳方法是什么slice1：slice2

  1. 最低代码
  2. 切片很大
  3. 切片未排序
  4. 不要修改切片
  5. 它们可能不包含重复项

这是我尝试过的：

slice1 := []string{"a", "b", "c", "d"}
slice2 := []string{"c", "d", "e", "f"}
duplicateItems := []string{}
for _, item1 := range slice1 {
    for _, item2 := range slice2 {
        if item1 == item2 {
            duplicateItems = append(duplicateItems, item1)
        }
    }
}

fmt.Println(duplicateItems) // [c d]

标签： arraysgoslice

解决方案

这种方法为大 O 复杂度（速度）牺牲了内存使用。

// flatten the first slice into a map for O(1) constant time lookup
m1 := make(map[string]struct{})
for _, v := range slice1 {
    m1[v] = struct{}{}
}

var dup []string

// iterate slice 2, using the O(1) lookup.
for _, v := range slice2 {
    if _, exists := m1[v]; exists {
        dup = append(dup, v)
    }
}

// dup contains the duplicates

您只访问每个元素一次，但内存需求要大得多，因为 slice1 需要存储在地图中。

您可以扩展此代码以将 2 个切片中最小的切片展平到地图中，从而减少内存需求。

值得注意的map[string]struct{}是使用而不是map[string]bool因为struct{}使用零字节的内存

推荐阅读