arrays - 从两个数组/切片中获取交集和排除的最有效方法是什么?
问题描述
给定两个数组或切片,例如:
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]
& 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
is a
,00000010
is b
,00000011
is a
and b
,and 00000000
is nether a
nor b
。|
操作员设置位,操作&
员读取位。
映射是一种类型的无序元素组,称为元素类型,由另一种类型的一组唯一键索引,称为键类型。
比较运算符 == 和 != 必须为键类型的操作数完全定义;因此键类型不能是函数、映射或切片。如果键类型是接口类型,则必须为动态键值定义这些比较运算符;失败将导致运行时恐慌。
该算法适用于其元素可以是映射键的任何切片类型。比较运算符 == 和 != 必须为键类型的操作数完全定义。
推荐阅读
- python - 在 Geopandas 中编辑颜色条(图例)?
- python - 如何将 asyncio 与其他操作系统线程同步?
- unix - 如果父进程和子进程附加到同一个文件,lseek() 和 write() 是否需要是原子的?
- algorithm - Tarjan算法和Kahn算法拓扑排序的区别
- java - 如果 boolean == false 则重新启动 while 循环
- r - 如何使用 systemfit 包进行诊断分析?
- excel - 搜索标题的最后一个实例
- c - 无法在 C 中获得正确的 CRC CCiTT
- python - SQLite DateTime 类型只接受 Python 日期时间
- javascript - 通过 rdflib.js 查询 Project Gutenberg catalog.rdf