专栏首页前端鼓励师从 0 开始学习 JavaScript 数据结构与算法(八)集合

从 0 开始学习 JavaScript 数据结构与算法(八)集合

集合

几乎每种编程语言中,都有集合结构。集合比较常见的实现方式是哈希表,这里使用 JavaScript 的 Object 进行封装。

集合特点

  • 集合通常是由一组无序的不能重复的元素构成。
  • 数学中常指的集合中的元素是可以重复的,但是计算机中集合的元素不能重复。
  • 集合是特殊的数组。
    • 特殊之处在于里面的元素没有顺序,也不能重复。
    • 没有顺序意味着不能通过下标值进行访问,不能重复意味着相同的对象在集合中只会存在一份。

封装集合

ES6 中的 Set 就是一个集合类,这里我们重新封装一个 Set 类,了解集合的底层实现。

集合常见的操作

  • add(value) 向集合添加一个新的项。
  • remove(value) 从集合移除一个值。
  • has(value) 如果值在集合中,返回 true,否则返回false
  • clear() 移除集合中的所有项。
  • size() 返回集合所包含元素的数量。与数组的 length 属性类似。
  • values() 返回一个包含集合中所有值的数组。
  • 还有其他的方法,用的不多,这里不做封装。

代码实现

// 集合结构的封装
class Set {
  constructor() {
    this.items = {};
  }

  // has(value) 判断集合中是否存在 value 值,存在返回 true,否则返回 false
  has(value) {
    return this.items.hasOwnProperty(value);
  }

  // add(value) 往集合中添加 value
  add(value) {
    if (this.has(value)) return false;
    this.items[value] = value;
    return true;
  }

  // remove(value) 删除集合中指定的 value
  remove(value) {
    // 如果集合不存在该 value,返回 false
    if (!this.has(value)) return false;
    delete this.items[value];
  }

  // clear() 清空集合中所有 value
  clear() {
    this.items = {};
  }

  // size() 获取集合中的 value 个数
  size() {
    return Object.keys(this.items).length;
  }

  // values() 获取集合中所有的 value
  values() {
    return Object.keys(this.items);
  }
}

代码测试

const set = new Set();

// add() 测试
set.add("abc");
set.add("abc");
set.add("123");
set.add("zxc");
console.log(set); //--> {items: {123: "123", abc: "abc", zxc: "zxc"}}

// has() 测试
console.log(set.has("123")); //--> true
console.log(set.has("456")); //--> false

// remove() 测试
set.remove("abc");
console.log(set); //--> {items: {123: "123", zxc: "zxc"}}

// size() 测试
console.log(set.size()); //--> 2

// values() 测试
console.log(set.values()); //--> ["123", "zxc"]

// clear() 测试
set.clear();
console.log(set.values()); //--> []

集合间的操作

  • 并集:对于给定的两个集合,返回一个包含两个集合中所有元素的新集合。
  • 交集:对于给定的两个集合,返回一个包含两个集合中共有元素的新集合。
  • 差集:对于给定的两个集合,返回一个包含所有存在于第一个集合且不存在于第二个集合的元素的新集合。
  • 子集:验证一个给定集合是否是另一个集合的子集。

image

并集的实现

// union() 求两个集合的并集
union(otherSet) {
    // 1、创建一个新集合
    let unionSet = new Set();

    // 2、将当前集合(this)的所有 value,添加到新集合(unionSet)中
    for (let value of this.values()) {
        unionSet.add(value);
    }

    // 3、将 otherSet 集合的所有 value,添加到新集合(unionSet)中
    for (let value of otherSet.values()) {
        unionSet.add(value); // add() 已经有重复判断
    }

    return unionSet;
}

交集的实现

// intersection() 求两个集合的交集
intersection(otherSet) {

    // 1、创建一个新集合
    let intersectionSet = new Set();

    // 2、从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在
    for (let value of this.values()) {
        if (otherSet.has(value)) {
            intersectionSet.add(value);
        }
    }

    return intersectionSet;
}

差集的实现

// difference() 差集
difference(otherSet) {

    // 1、创建一个新集合
    let differenceSet = new Set();

    // 2、从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在,不存在的即为差集
    for (let value of this.values()) {
        if (!otherSet.has(value)) {
            differenceSet.add(value);
        }
    }

    return differenceSet;
}

子集的实现

// subset() 子集
subset(otherSet) {

    // 从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在,有不存在的返回 false
    // 遍历完所有的,返回 true
    for (let value of this.values()) {
        if (!otherSet.has(value)) {
            return false;
        }
    }
    return true;
}

集合的完整实现

// 集合结构的封装
export default class Set {
  constructor() {
    this.items = {};
  }

  // has(value) 判断集合中是否存在 value 值,存在返回 true,否则返回 false
  has(value) {
    return this.items.hasOwnProperty(value);
  }

  // add(value) 往集合中添加 value
  add(value) {
    if (this.has(value)) return false;
    this.items[value] = value;
    return true;
  }

  // remove(value) 删除集合中指定的 value
  remove(value) {
    // 如果集合不存在该 value,返回 false
    if (!this.has(value)) return false;
    delete this.items[value];
  }

  // clear() 清空集合中所有 value
  clear() {
    this.items = {};
  }

  // size() 获取集合中的 value 个数
  size() {
    return Object.keys(this.items).length;
  }

  // values() 获取集合中所有的 value
  values() {
    return Object.keys(this.items);
  }

  // ------- 集合间的操作 ------- //
  // union() 求两个集合的并集
  union(otherSet) {
    // 1、创建一个新集合
    let unionSet = new Set();

    // 2、将当前集合(this)的所有 value,添加到新集合(unionSet)中
    for (let value of this.values()) {
      unionSet.add(value);
    }

    // 3、将 otherSet 集合的所有 value,添加到新集合(unionSet)中
    for (let value of otherSet.values()) {
      unionSet.add(value); // add() 已经有重复判断
    }

    return unionSet;
  }

  // intersection() 求两个集合的交集
  intersection(otherSet) {
    // 1、创建一个新集合
    let intersectionSet = new Set();

    // 2、从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在
    for (let value of this.values()) {
      if (otherSet.has(value)) {
        intersectionSet.add(value);
      }
    }

    return intersectionSet;
  }

  // difference() 差集
  difference(otherSet) {
    // 1、创建一个新集合
    let differenceSet = new Set();

    // 2、从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在,不存在的即为差集
    for (let value of this.values()) {
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    }

    return differenceSet;
  }

  // subset() 子集
  subset(otherSet) {
    // 从当前集合中取出每一个 value,判断是否在 otherSet 集合中存在,有不存在的返回 false
    // 遍历完所有的,返回 true
    for (let value of this.values()) {
      if (!otherSet.has(value)) {
        return false;
      }
    }
    return true;
  }
}

本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

参考资料

[1]

GitHub 仓库: https://github.com/XPoet/js-data-structures-and-algorithms

专辑:

从 0 开始学习 JavaScript 数据结构与算法(一)前言

从 0 开始学习 JavaScript 数据结构与算法(二)数组结构

从 0 开始学习 JavaScript 数据结构与算法(三)栈

从 0 开始学习 JavaScript 数据结构与算法(四)队列

从 0 开始学习 JavaScript 数据结构与算法(五)优先队列

从 0 开始学习 JavaScript 数据结构与算法(六)单向链表

从 0 开始学习 JavaScript 数据结构与算法(七)双向链表

本文分享自微信公众号 - 前端鼓励师(FE-Cheerleaders),作者:XPoet

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2021-04-05

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 从 0 开始学习 JavaScript 数据结构与算法(三)栈

    数组是一个线性结构,并且可以在数组的任意位置插入和删除元素。但是有时候,我们为了实现某些功能,必须对这种任意性加以限制。栈和队列就是比较常见的受限的线性结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十一)树

    如图,树结构的组成方式类似于链表,都是由一个个节点连接构成。不过,根据每个父节点子节点数量的不同,每一个父节点需要的引用数量也不同。比如节点 A 需要 3 个引...

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十二)图

    在计算机程序设计中,图也是一种非常常见的数据结构,图论其实是一个非常大的话题,在数学上起源于哥尼斯堡七桥问题。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(九)字典

    本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(四)队列

    队列(Queue)是一种运算受限的线性表,特点:先进先出。(FIFO:First In First Out)

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(十)哈希表

    哈希表是一种非常重要的数据结构,几乎所有的编程语言都直接或者间接应用这种数据结构。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(五)优先队列

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(六)单向链表

    单向链表类似于火车,有一个火车头,火车头会连接一个节点,节点上有乘客,并且这个节点会连接下一个节点,以此类推。

    XPoet
  • 从 0 开始学习 JavaScript 数据结构与算法(七)双向链表

    本专辑所有文章&源码&测试环境均托管在 GitHub 仓库[1] 欢迎同学们 Star 和 Fork。

    XPoet
  • 从0开始的Python学习012数据结构&对象与类

    在Python中三种内建的数据结构--列表、元组和字典。学会了使用它们会使编程变得的简单。

    Happy、Liu
  • 数据结构与算法学习笔记之 从0编号的数组

    数组看似简单,但掌握精髓的却没有多少;他既是编程语言中的数据类型,又是最基础的数据结构;

    Dawnzhang
  • 从Go语言开始,彻底学懂数据结构与算法 -- 线性表

    用一个定长数组data[]存储数据,最大空间为Maxsize,用length记录实际的元素个数,即数组的长度。

    宇宙之一粟
  • 数据结构与算法学习笔记之先进先出的队列 数据结构与算法学习笔记之写链表代码的正确姿势(下)数据结构与算法学习笔记之 提高读取性能的链表(上)数据结构与算法学习笔记之 从0编号的数组数据结构与算法学

      队列是一种非常实用的数据结构,类似于生活中发排队,可应用于生活,开发中各个方面,比如共享打印机(先请求先打印),消息队列。你想知道他们是怎么工作的么。那就来...

    Dawnzhang
  • PHP数据结构(十) ——有向无环图与拓扑算法

    PHP数据结构(十)——有向无环图与拓扑算法 (原创内容,转载请注明来源,谢谢) 一、有向无环图概念 有向无环图又称为DAG图。与其对应的还有有向树、有环图。...

    用户1327360
  • 全栈开发自学日志(持续更新)

    筑梦师winston
  • 【译】《Understanding ECMAScript6》- 第一章-基础知识(二)

    块绑定 JavaScript中使用var进行变量声明的机制非常怪异。在大多数C系列的编程语言中,变量的创建是在被声明的时刻同时进行的。但是JavaScript并...

    寒月十八
  • 重读《学习JavaScript数据结构与算法-第三版》- 第4章 栈

    本章是重读《学习JavaScript数据结构与算法-第三版》的系列文章,本章为各位小伙伴分享数据结构-栈的故事,请让胡哥带你走进栈的世界

    胡哥有话说
  • 布客·ApacheCN 翻译校对活动进度公告 2020.5

    参与方式:https://github.com/apachecn/interpretable-ml-book-zh/blob/master/CONTRIBUTI...

    ApacheCN_飞龙
  • 数据结构与算法学习笔记之 适合大规模的数据排序 数据结构与算法学习笔记之如何分析一个排序算法?

    在数据排序的算法中,不同数据规模应当使用合适的排序算法才能达到最好的效果,如小规模的数据排序,可以使用冒泡排序、插入排序,选择排序,他们的时间复杂度都为O(n...

    Dawnzhang

扫码关注云+社区

领取腾讯云代金券