技巧:快速求并集交集和差集

栏目: PHP · 发布时间: 5年前

内容简介:在做一个文件同步工具的时候,有这样一个需求:假设有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)。

感谢阅读,希望这篇文章能给你带来帮助!

技巧:快速求并集交集和差集


以上所述就是小编给大家介绍的《技巧:快速求并集交集和差集》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Java学习指南(第4版)(上下册)

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版)(上下册)》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML 在线格式化
XML 在线格式化

在线 XML 格式化压缩工具

正则表达式在线测试
正则表达式在线测试

正则表达式在线测试