从两个数组/切片中获取交集和排除项的最有效方法是什么?

给出两个数组或切片,例如:</ p>

  a:  = [] int {1、2、3、4、5} 
b:= [] int {3、4、5、6、7、8、9}
</ code> </ pre>
\ n

切片可能没有排序,顺序也无所谓。</ p>

最有效的计算值方法是,您最终得到两个切片的共同元素, 而其余元素出现在一个元素中却没有另一个元素,即上面给出的两个数组的返回值将是:</ p>

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

计算相交点,将一个切片转换为地图,然后在该切片上进行迭代以查看值是否存在。 有没有一种方法可以计算同一循环中的其他两个值?</ p>
</ div>

展开原文

原文

Given two arrays or slices for eg:

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

The slices may not be sorted and order doesn't matter.

What is the most efficient way to compute values such that you end up with the common elements of both slices, and the remainder of elements present in one but not the other i.e for the two arrays given above the return values would be:

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

Its easy to compute the intersection converting one slice into a map and then iterating over the one to see if values exist. Is there a way to compute the other two values within the same loop?

donglizhan7848
donglizhan7848 这取决于值的大小和分布。花一些时间在图书馆里。所述问题与Go无关。
大约 2 年之前 回复
dpkt17803
dpkt17803 切片可能没有排序,顺序也没关系
大约 2 年之前 回复
dongya0914
dongya0914 将两个切片的数据插入到地图中,然后检查是否存在元素,该元素将告诉您哪个元素是常见的。
大约 2 年之前 回复
ds34222
ds34222 您的数组(实际上是切片!)是否始终排序(如示例中所示)?您需要保留原始切片还是可以更改这些切片?
大约 2 年之前 回复

1个回答

O(len(a) + len(b)) is efficient. For example,

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)
}

Playground: https://play.golang.org/p/RvGaC9Wfjiv

Output:

[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

We have 8 bits for uint8. Bit 0 (1 << 0, 1 shift left 0) is a and bit 1 (1 << 1; 1 shift left 1) is b. For uint8 bits, 00000001 is a, 00000010 is b, 00000011 is a and b, and 00000000 is nether a nor b. The | operator sets a bit, the & operator reads a bit.


The Go Programming Language Specification

Map types

A map is an unordered group of elements of one type, called the element type, indexed by a set of unique keys of another type, called the key type.

The comparison operators == and != must be fully defined for operands of the key type; thus the key type must not be a function, map, or slice. If the key type is an interface type, these comparison operators must be defined for the dynamic key values; failure will cause a run-time panic.

The algorithm works for any slice type whose elements can be a map key. The comparison operators == and != must be fully defined for operands of the key type.

duansanzi5265
duansanzi5265 请参阅我的修订答案,以获取对您评论中问题的答案。
大约 2 年之前 回复
dt3696912
dt3696912 这是对a进行哈希处理或排序的代码,以获取a&b(交集)和a-b(差异)。 (对于b-a,您可以将a和b交换来运行相同的代码。)play.golang.org/p/FcX8OIAGVH4
大约 2 年之前 回复
dongtaihui5131
dongtaihui5131 (更正我先前的评论(为时已晚),如果您不能进行哈希处理,则可以从根据要执行的操作对一个数组进行排序开始。)
大约 2 年之前 回复
doubao6681
doubao6681 是的,要接受这个答案。 谢谢!
大约 2 年之前 回复
doulu8415
doulu8415 如果结构中的所有内容都可以是地图键,则它们可以是地图键。 否则,您可能需要一种从对数组进行排序开始的方法。
大约 2 年之前 回复
duandun3178
duandun3178 我喜欢这个答案,但是如果切片是[] struct {}呢? 仍然可以使用吗?
大约 2 年之前 回复
dphj737575
dphj737575 真棒! 我不太了解按位运算符。 您能解释一下它的作用吗:对于_,k:=范围a {m [k] | =(1 << 0)}对于_,k:=范围b {m [k] | =(1 << 1) },这a:= v&(1 << 0)!= 0 b:= v&(1 << 1)!= 0
大约 2 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问