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

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

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

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


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

查看所有标签

猜你喜欢:

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

Making Things See

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》 这本书的介绍吧!

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

MD5 加密
MD5 加密

MD5 加密工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具