用js来实现那些数据结构10(集合02-集合的操作)

  前一篇文章我们一起实现了自定义的set集合类。那么这一篇我们来给set类增加一些操作方法。那么在开始之前,还是有必要解释一下集合的操作有哪些。便于我们更快速的理解代码。

  1、并集:对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。注意,集合中不会有重复的值。  

  2、交集:对于给定的两个集合,返回一个包含两个集合中共有元素的新集合。

  3、差集:对于给定的集合,返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。简单来说就是我有你没有的元素。

  4、验证一个给定集合是否是另一个集合的子集。

  这里我们就不详细的再赘述一遍集合操作的数学计算方法了。有兴趣或者忘记了的小伙伴可以百度一下。那么咱们就正式开始集合的操作方法。

一、并集

//并集操作
this.union = function (otherSet) {
    //存储两个集合元素的新集合,后面我们会把它作为返回值返回。
    let unionSet = new Set();
    //values为当前set的数组列表
    let values = this.values();
    //循环加入
    for(let i = 0; i < values.length; i++) {
        unionSet.add(values[i]);
    }
    //重新复制values
    values = otherSet.values();
    //把otherSet的值循环存入unionSet,由于我们的add不会加入重复的值,自然在unionSet中就不会出现重复的值
    for(let i = 0; i < values.length; i++) {
        unionSet.add(values[i]);
    }

    return unionSet;
}

  我们发现,其实并集的操作十分简单,就是声明一个新的set,然后通过循环两个setA和setB中的值存入新的unionSet中就可以了。一点都不复杂

let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);
let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);


let unionAB = setA.union(setB);
console.log(unionAB.values());// [1, 2, 3, 4, 5, 6]

二、交集

//交集操作
this.intersection = function (otherSet) {
  let intersectionSet = new Set();

  let values = this.values();
  for (let i = 0; i < values.length; i++) {
      if(otherSet.has(values[i])) {
          intersectionSet.add(values[i])
      }
  }

  return intersectionSet;
}

  交集操作其实十分简单,一句话就是检查setA中的元素是否在setB中也有,如果有那么久存入intersectionSet中。就跟我们要查找两个数组中是否有相同的元素是一个道理。

let setC = new Set();
setC.add(5);
setC.add(6);
setC.add(7);

let setD = new Set();
setD.add(5);
setD.add(7);
setD.add(4);
setD.add(8);

let intersectionSetCD = setC.intersection(setD);
console.log(intersectionSetCD.values());//[5,7]

三、差集

//差集操作
this.difference = function (otherSet) {
  let differenceSet = new Set();

  let values = this.values();
  for (let i = 0; i < values.length; i++) {
      //只是比交集操作这里的判断改成了非(!)而已
      if(!otherSet.has(values[i])) {
          differenceSet.add(values[i])
      }
  }

  return differenceSet;
}

  差集的操作和并集的操作十分类似。并集是需要两个集合中都存在的元素(你有我也有),而差集是存在于setA中但是不存在于setB中(你有我没有)。

  所以我们只需要稍微更改一下交集的代码就可以了。

let setM = new Set();
setM.add(5);
setM.add(6);
setM.add(7);

let setN = new Set();
setN.add(5);
setN.add(7);
setN.add(4);
setN.add(8);


let differenceSetMN = setM.difference(setN);
console.log(differenceSetMN.values());//[6]

四、子集

//子集操作
this.subset = function (otherSet) {
    if(this.size() > otherSet.size()) {
        return false;
    } else {
        let values = this.values();
        for (let i = 0; i < values.length; i++) {
            if(!otherSet.has(values[i])) {
                return false;
            }
        }
        return true;
    }
}

  其实子集操作也没什么好解释的,只是要注意的是如果setA的子集是setB,那么setA的元素个数是一定大于或等于setB的。否则setB就不可能是setA的子集。所以我们在最开始就判断元素的size是否符合这个定义。

  那么如果符合,我们在遍历整个setB的元素,判断在setA中是否存在,只要有不存在的就直接返回false,如果遍历结束都存在,那么才返回true。

let setX = new Set();
setX.add(1);
setX.add(2);

let setY= new Set();
setY.add(1);
setY.add(2);
setY.add(3);

let setZ= new Set();
setZ.add(2);
setZ.add(3);
setZ.add(4);

console.log(setX.subset(setY));//true
console.log(setX.subset(setZ));//false

  这里我们就介绍完了集合的操作,是不是十分简单。那么接下来我们来看看ES6原生的set类是什么样子的。

ES6原生Set类

我们先来看看原生set类的简单例子:

let set = new Set();
set.add(1);
console.log(set.values());//SetIterator {1}
set.add(2);
console.log(set.has(1));//true
console.log(set.size)//2
console.log(set.delete(1));//true
console.log(set.size)//1
console.log(set.has(1));//false
console.log(set.has(2));//true

  原生Set类拥有has()、add()、delete()、clear()等方法。也拥有values()、keys()、entries()、forEach()等遍历方法,还拥有一个size属性。这里不会详细的介绍每一个属性方法,想要深入学习大家可以自行去查阅。

  那么我们看看如何用原生Set类来操作集合。

let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);



//模拟并集操作
let unionAb = new Set();
//其实跟我们自定义并集操作的原理是一样的,分别遍历两个集合并把其元素加入到unionAb中
//for...of 这种操作也是ES6的循环遍历方法。
for (let x of setA) unionAb.add(x);
for (let x of setB) unionAb.add(x);
console.log(unionAb.values())//SetIterator {1, 2, 3, 4}

//模拟交集操作
//模拟交集操作需要创建一个辅助函数,来生成包含setA和setB都有的元素的新集合。
let intersetion = function (setA,setB) {
    let intersetionSet = new Set();

    for(let x of setA) {
        if(setB.has(x)) {
            intersetionSet.add(x);
        }
    }

    return intersetionSet;
}

let intersetionAb = intersetion(setA,setB);
console.log(intersetionAb.values())//SetIterator {2, 3}


//模拟差集操作
//同样的,跟交集操作极为类似,只是判断条件刚好相反罢了
let difference = function (setA,setB) {
    let differenceSet = new Set();

    for(let x of setA) {
        if(!setB.has(x)) {
            differenceSet.add(x);
        }
    }

    return differenceSet;
}

let differenceAb = difference(setA,setB);
console.log(differenceAb.values())//SetIterator {1}

  在写完了ES6原生Set类模拟集合操作的时候,我们发现跟我们自定义的集合操作方法极为相似。只是我们使用了ES6原生的接口罢了。大家可以尝试着对比一下这两种类型的代码。加深印象。

  到这里集合就介绍完毕了。回顾一下代码,我们发现其实集合的各种操作方法在我们的实际工作中也是经常应用到的,只是我们在用数组操作,并没有十分的去注意这些细节。比如并集操作,我们在合并两个数组的时候肯定用到过。比如交集操作,我们在查找两个数组中公共元素的时候就会用到。所以其实我们在工作中已经用过或者说经常使用这些类似于集合操作的思想。

  最后,由于本人水平有限,能力与大神仍相差甚远,若有错误或不明之处,还望大家不吝赐教指正。非常感谢!

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏blackheart的专栏

[C#6] 4-string 插值

0. 目录 C#6 新增特性目录 1. 老版本的代码 1 internal class Person 2 { 3 public string Na...

21260
来自专栏GreenLeaves

C#核编之格式化编程

一、格式化控制台输入输出     1、 在前面的随笔中,会经常看到诸如{0},{1}之类的标记嵌入在字符串变量中。.NET引入一种字符串格式化的新风格。与C的p...

211100
来自专栏Road

Redis 设计 --- 高效数据结构实现剖析

即使有链表来处理键冲突,但是当节点数量远远大于 size 时,如果不扩充哈希表规模,请自行想象。这也是 rehash 的存在意义,笔者认为这也是 redis 扩...

15430
来自专栏Java与Android技术栈

Java8 Stream的总结

Stream是Java 8新增的接口,Stream可以认为是一个高级版本的 Iterator。它代表着数据流,流中的数据元素的数量可以是有限的,也可以是无限的。

12420
来自专栏博客园

.NET Core中延迟单例另一种写法【.NET Core和.NET Framework的beforefieldinit差异】

   前段时间在反编译代码时无意间看到在类中有一个BeforeFieldInit特性,处于好奇的心态查了查这个特性,发现这是一个关于字段初始化时间的特性【提前初...

19440
来自专栏蘑菇先生的技术笔记

探索c#之递归APS和CPS

31270
来自专栏Golang语言社区

厚土Go学习笔记 | 28. go语言没有类 却可以在结构体或任意类型定义方法

在go语言中没有类。可是,是有方法的。 给结构体定义方法,在对应的 func 和方法名之间,加上方法的接收者就可以了。 比如,我们定义了一个结构体 type V...

38580
来自专栏分布式系统和大数据处理

.Net中的反射(查看类型信息) - Part.2

简单来说,反射提供这样几个能力:1、查看和遍历类型(及其成员)的基本信息和程序集元数据(metadata);2、迟绑定(Late-Binding)方法和属性。3...

13330
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(Function专栏)

汇总系列:https://www.cnblogs.com/dunitian/p/4822808.html#ai

9830
来自专栏逸鹏说道

Python3 与 C# 基础语法对比(Function专栏)

汇总系列:https://www.cnblogs.com/dunitian/p/4822808.html#ai

18350

扫码关注云+社区

领取腾讯云代金券