从两个数组/切片中获取交集和差集的最有效方法是什么？

Question

从两个数组/切片中获取交集和差集的最有效方法是什么？

4

给定两个数组或切片，例如：

a := []int{1, 2, 3, 4, 5}
b := []int{3, 4, 5, 6, 7, 8, 9}

切片可能未排序，顺序不重要。

计算值的最有效方法是什么，以便您最终获得两个切片的公共元素和一个中存在但另一个中不存在的元素，即对于上面给出的两个数组，返回值将是：

common := []int{3, 4, 5}
inAButNotB := []int{1, 2}
inBButNotA := []int{6, 7, 8, 9}

将一个切片转换为映射并遍历该映射以查看值是否存在，计算交集非常容易。是否有一种方法可以在同一个循环中计算另外两个值？

- ziyadparekh

你的数组（实际上是切片！）总是排序好的吗（就像示例中一样）？你需要保留原始切片还是可以更改它们？ - ain

将两个切片的数据插入到一个映射中，然后检查元素出现的次数，这将告诉您哪个元素是共同的。 - Himanshu

1

数组切片可能未排序，且顺序无关紧要。 - ziyadparekh

这取决于大小和值的分布。在图书馆花些时间。所提出的问题与Go无关。 - Volker

这个回答解决了你的问题吗？如何在Go中获取两个切片的交集？ - dikkini

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- peterSO · Accepted Answer

O(len(a) + len(b)) 是高效的。例如，

package main

import (
    "fmt"
)

func main() {
    a := []int{1, 2, 3, 4, 5}
    b := []int{3, 4, 5, 6, 7, 8, 9}
    fmt.Println(a)
    fmt.Println(b)

    m := make(map[int]uint8)
    for _, k := range a {
        m[k] |= (1 << 0)
    }
    for _, k := range b {
        m[k] |= (1 << 1)
    }

    var inAAndB, inAButNotB, inBButNotA []int
    for k, v := range m {
        a := v&(1<<0) != 0
        b := v&(1<<1) != 0
        switch {
        case a && b:
            inAAndB = append(inAAndB, k)
        case a && !b:
            inAButNotB = append(inAButNotB, k)
        case !a && b:
            inBButNotA = append(inBButNotA, k)
        }
    }
    fmt.Println(inAAndB)
    fmt.Println(inAButNotB)
    fmt.Println(inBButNotA)
}

演示代码：https://play.golang.org/p/RvGaC9Wfjiv

输出结果：

[1 2 3 4 5]
[3 4 5 6 7 8 9]
[3 4 5]
[1 2]
[8 6 7 9]

The Go Programming Language Specification

&    bitwise AND            integers
|    bitwise OR             integers
^    bitwise XOR            integers
&^   bit clear (AND NOT)    integers

<<   left shift             integer << unsigned integer
>>   right shift            integer >> unsigned integer

我们对于uint8有8个比特位。比特0（1 << 0，1向左移动0位）代表a，比特1（1 << 1，1向左移动1位）代表b。对于uint8的比特位，00000001代表a，00000010代表b，00000011代表a和b，00000000代表既不是a也不是b。|运算符用于设置某个比特位，&运算符用于读取某个比特位。

Go编程语言规范

映射类型

映射是一组无序的元素，元素类型为一种类型，称为元素类型，由另一种类型的一组唯一键索引，称为键类型。

对于键类型，必须完全定义比较操作符==和!=；因此，键类型不能是函数、映射或切片。如果键类型是接口类型，则必须为动态键值定义这些比较操作符；否则将引发运行时恐慌。

该算法适用于任何元素类型可以作为映射键的切片类型。对于键类型，必须完全定义比较操作符==和!=。