给出两个数组或切片,例如:
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}
它很容易计算将一个切片转换为一个切片然后迭代一个切片以查看是否存在值的交点。有没有办法计算同一循环中的其他两个值?
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
我们有8位用于uint8
。位0(1 << 0
,1位左0)是a
和位1(1 << 1
; 1位左移1)是b
。对于uint8
位,00000001
是a
,00000010
是b
,00000011
是a
和b
,而00000000
是nether a
和b
。 |
运算符设置了一点,&
运算符读取了一点。
The Go Programming Language Specification
映射是一种无序的一类元素,称为元素类型,由一组另一种类型的唯一键索引,称为键类型。
必须为键类型的操作数完全定义比较运算符==和!=;因此,键类型不能是函数,映射或切片。如果密钥类型是接口类型,则必须为动态密钥值定义这些比较运算符;失败会导致运行时恐慌。
该算法适用于任何切片类型,其元素可以是地图关键字。必须为键类型的操作数完全定义比较运算符==和!=。