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

Question

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?

Answer 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.