内容简介:在做一个文件同步工具的时候,有这样一个需求:假设有source和target两个文件夹,确保两个文件夹中的文件一致。即当source中添加了新文件时,自动拷贝到target; 当source文件夹删除某个文件时,target中的文件也要删除。(实际上文件改动也要进行同步,但和这个例子没有关系)。这样就需要求两个集合的差集,这篇文章演示如何快速实现这一过程。下面这幅图可以说明要执行的操作:直观上,最容易想到的方法就是嵌套两个for循环来遍历这两个集合,但这样的时间复杂度是O(n^2)。一个更好的办法,是借助H
在做一个文件同步 工具 的时候,有这样一个需求:假设有source和target两个文件夹,确保两个文件夹中的文件一致。即当source中添加了新文件时,自动拷贝到target; 当source文件夹删除某个文件时,target中的文件也要删除。(实际上文件改动也要进行同步,但和这个例子没有关系)。这样就需要求两个集合的差集,这篇文章演示如何快速实现这一过程。
下面这幅图可以说明要执行的操作:
直观上,最容易想到的方法就是嵌套两个for循环来遍历这两个集合,但这样的时间复杂度是O(n^2)。一个更好的办法,是借助Hash表的快速访问能力来将嵌套的for循环改为单个的for循环。
下面是 go 语言的实现:
package main import ( "fmt" "strings" ) func main() { source := []string{"apple", "banana", "pear", "watermelon", "strawberry"} target := []string{"pear", "watermelon", "strawberry", "orange", "litchi"} set := getSetDiff(source, target) all := []string{} // 并集 add := []string{} // source和target的差集 del := []string{} // target和source的差集 both := []string{} // 交集 for k, v := range set { if v == 1 { add = append(add, k) } if v == 0 { both = append(both, k) } if v == -1 { del = append(del, k) } all = append(all, k) } fmt.Printf("并集: %v\n", strings.Join(all[:], ",")) fmt.Printf("交集: %v\n", strings.Join(both[:], ",")) fmt.Printf("source和target的差集: %v\n", strings.Join(add[:], ",")) fmt.Printf("target和source的差集: %v\n", strings.Join(del[:], ",")) } func getSetDiff(source, target []string) map[string]int { var m = make(map[string]int) for _, item := range source { m[item] = 1 // 差集 source-target } for _, item := range target { if _, ok := m[item]; ok { m[item] = 0 // source 和 target中都有的 } else { m[item] = -1 // 差集 target-source } } return m }
输出的结果如下:
并集: apple,banana,pear,watermelon,strawberry,orange,litchi 交集: pear,watermelon,strawberry source和target的差集: apple,banana target和source的差集: orange,litchi
在需要反复进行集合遍历的操作时,都可以考虑下是否有使用hash表的替代方案,使用hash表的速度往往要快很多,它存取数据的时间复杂度是:O(1),而使用for循环对列表进行线性查找的时间复杂度是O(n)。
感谢阅读,希望这篇文章能给你带来帮助!
以上所述就是小编给大家介绍的《技巧:快速求并集交集和差集》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 【 数据集合】并集、交集、差集、子集
- JS实现的集合去重,交集,并集,差集功能示例
- C++拾取——stl标准库中集合交集、并集、差集、对等差分方法
- LeetCode每日一题:两个数组的交集(No.349)
- LeetCode 349:两个数组的交集 Intersection of Two Arrays
- 对话灵雀云CTO陈恺:迁移上云需求和云原生技术已经产生交集
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Making Things See
Greg Borenstein / Make / 2012-2-3 / USD 39.99
Welcome to the Vision Revolution. With Microsoft's Kinect leading the way, you can now use 3D computer vision technology to build digital 3D models of people and objects that you can manipulate with g......一起来看看 《Making Things See》 这本书的介绍吧!