内容简介:在做一个文件同步工具的时候,有这样一个需求:假设有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陈恺:迁移上云需求和云原生技术已经产生交集
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Java学习指南(第4版)(上下册)
Patrick Niemeyer、Daniel Leuck / 李强、王建新、吴戈 / 人民邮电出版社 / 2014-7 / 128.00元
《Java学习指南(第4版)(上、下册)》是畅销Java学习指南的最新版,详细介绍了Java 6和Java 7的语言特性和API。本书全面介绍了Java的基础知识,力图通过完备地介绍Java语言、其类库、编程技术以及术语,从而成为一本名符其实的入门级图书。 《Java学习指南(第4版)(上、下册)》加入了从Java 6和Java 7发布以后的变化,包括新的语言功能、并发工具(Fork-Joi......一起来看看 《Java学习指南(第4版)(上下册)》 这本书的介绍吧!