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

栏目: 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)。

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

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


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

查看所有标签

猜你喜欢:

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

翻转课堂的可汗学院

翻转课堂的可汗学院

萨尔曼·可汗(Salman Khan) / 刘婧 / 浙江人民出版社 / 2014-4-1 / 49.00元

MIT和哈佛毕业的高材生缘何放弃金融分析师工作投身教育事业?YouTube上的“可汗学院频道”至今共吸引了163.3万订阅者,观看次数超过3.55亿次,它为什么如此大受欢迎?创始人萨尔曼·可汗阐述属于未来的教育理念——让地球上的任何人都能随时随地享受世界一流的免费教育! 现行教育模式已有200余年历史,可汗认为,在互联网蓬勃发展、社交网络盛况空前的时代,免费、灵活、适合个体、全球共享的教育才......一起来看看 《翻转课堂的可汗学院》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

URL 编码/解码
URL 编码/解码

URL 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具