给定两个数组或 slice ,例如:
a := []int{1, 2, 3, 4, 5}
b := []int{3, 4, 5, 6, 7, 8, 9}
slice 可能未排序,顺序无关紧要。
计算值的最有效方法是什么,这样您最终得到两个 slice 的公共(public)元素,并且剩余元素存在于一个 slice 中但不存在于另一个 slice 中,即对于上面给出的两个数组,返回值将是:
common := []int{3, 4, 5}
inAButNotB := []int{1, 2}
inBButNotA := []int{6, 7, 8, 9}
计算交集很容易,只需将一个 slice 转换为 map ,然后遍历该 slice 以查看值是否存在。有没有办法在同一个循环中计算其他两个值?
最佳答案
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)
}
Playground :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 位. Bit 0 ( 1 << 0
, 1 shift left 0) is a
位 1(1 << 1
;1 左移 1)是 b
.对于 uint8
位,00000001
是a
, 00000010
是b
, 00000011
是a
和 b
, 和 00000000
是下界a
也不b
. |
运算符设置位,&
运算符(operator)读取了一点。
The Go Programming Language Specification
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.
该算法适用于其元素可以是映射键的任何 slice 类型。必须为键类型的操作数完全定义比较运算符 == 和 !=。
关于arrays - 从两个数组/slice 中获取交集和排除项的最有效方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/52120488/