【化解数据结构】详解集合结构，并实现一个集合

转x33g5p2x  于2021-12-30 转载在 其他  
字(4.5k)|赞(0)|评价(0)|浏览(435)

📢 大家好，我是小丞同学，一名大二的前端爱好者

📢 这篇文章将讲解数据结构中的集合

📢 非常感谢你的阅读，不对的地方欢迎指正 🙏

📢 愿你忠于自己，热爱生活

💡 知识点抢先看

  • 什么是集合？
  • 集合有哪些方法
  • 实现一个集合
  • 集合有哪些操作方式
  • LeetCode 实战

📢 碎碎念
在之前的文章中，我们学习了 3 种线性结构，接下来我们需要学习的集合，我更倾向于把它称作是一个容器，它有着十分强大的方法和效率，我们一起来学习吧~

一、什么是集合？

集合是由一组无序且唯一（即不能重复）的项组成的，它具有数学中有限集合的性质。

在数学中，集合是一组不同的对象，比如：

的自然数集合：N = {0, 1, 2, 3, 4, 5, 6, …} ，集合中的对象采用花括号包围

上图就可以表示一个集合，它具有唯一性和无序性

接下来我们一起来实现一个集合吧~

二、集合有哪些方法？

在 ES6 中新增了一个 Set 类，可以通过它来快速的创建一个集合，在这里我们自己实现一个 Set 类

在上面我们说到，我们使用一个对象来创建集合（也可以使用数组）

当然选择对象来创建会更加方便一点，在 JavaScript 的对象中不允许一个键指向两个不同的属性，这保证了集合里的元素都是唯一的

在这里我们需要给集合添加一下这些方法

方法含义
add(value)向集合中添加一个新的元素
remove(value)从集合移除一个值
has(value)判断集合中是否存在某个值
clear()清空集合
size()返回集合中的元素数量
values()返回集合中所有值的数组

三、手写实现一个集合

1. 创建一个 Set 类

利用对象来创建一个集合

  1. class Set {
  2.     constructor () {
  3.         this.data = {}
  4.     }
  5. }

接下来开始封装方法

2. 实现 has 方法

在实现 add 方法之前，需要先来实现一个 has 方法

  1. has(value) {
  2.     return value in this.data
  3. }

这里我们采用 in 操作符，判断 value 是否存在于 data 对象中，如果有就返回 true 即可

3. 实现 add 方法

由于集合存在唯一性的特点，因此我们需要在添加元素之前，判断当前集合中，是否存在当前元素，如果不存在就添加到集合当中，返回添加成功 true ，如果存在则返回 false 未添加

  1. add(value) {
  2.     if(!this.has(value)) {
  3.         this.data[value] = value
  4.         return true
  5.     }
  6.     return false
  7. }

在这里我们先通过 has 方法来判断是否有值，没有的话添加到集合中

4.实现 remove 方法

remove 方法从集合中移出一个元素，它接受需要移出的元素作为参数

  1. remove (value) {
  2.     if(this.has(value)) {
  3.         delete this.data[value]
  4.         return true
  5.     }
  6.     console.log('未找到需要删除的元素');
  7.     return false
  8. }

在这里先通过 has 方法来判断是否有这个值，有的话采用 delete 删除元素，没有提示未找到

5. 实现 clear 方法

clear 方法清空整个集合，我们同样可以采用重置对象的方式来实现

  1. clear() {
  2.     this.data = {}
  3. }

6. 实现 size 方法

实现 size 有很多种方法

第一种

可以利用 object 类的内置方法 keys ，它能够返回一个给定对象所有属性的数组

因此我们可以采用 length 方法来获取它的长度

  1. size() {
  2.     return Object.keys(this.data).length
  3. }

第二种

我们可以手动提取 data 对象上的每个属性，记录属性的个数

  1. size() {
  2.     let count = 0;
  3.     // 遍历对象
  4.     for(let prop in this.data) {
  5.         if(this.data.hasOwnProperty(prop)) {
  6.             ++count
  7.         }
  8.     }
  9.     return count
  10. }

在这里我们还需要使用对象的 hasOwnProperty 方法来判断，这个属性是不是原型上的方法，因为对象种包含了很多内置的方法，采用 for-in 遍历时，会遍历到不是集合中的值

简单一点使用第一种方法即可

7. values 方法

我们需要将 data 集合，转化成一个数组，我们可以采用之前用到的 keys 方法来实现

  1. values() {
  2.     return Object.keys(this.data)
  3. }

8. 完整 Set 实现

  1. class Set {
  2.     constructor() {
  3.         this.data = {}
  4.     }
  5.     has(value) {
  6.         return value in this.data
  7.     }
  8.     add(value) {
  9.         if (!this.has(value)) {
  10.             this.data[value] = value
  11.             return true
  12.         }
  13.         return false
  14.     }
  15.     remove(value) {
  16.         if (this.has(value)) {
  17.             delete this.data[value]
  18.             return true
  19.         }
  20.         console.log('未找到需要删除的元素');
  21.         return false
  22.     }
  23.     clear() {
  24.         this.data = {}
  25.     }
  26.     size() {
  27.         return Object.keys(this.data).length
  28.     }
  29.     values() {
  30.         return Object.keys(this.data)
  31.     }
  32. }

9. 如何使用 Set 方法

我们只需要通过 new 方法来构造一个实例对象即可操作它

  1. const set = new Set()

添加元素

  1. set.add(2)
  2. set.add(3)

删除元素

  1. set.remove(3)
  2. set.remove(4) // 未找到需要删除的元素

四、集合操作方法

在数学中，我们常常做到一些求，交集，求并集，求子集差集的操作，在这里我们也可以实现

方法含义
union()并集
intersection()交集
difference()差集
subset()差集

1. 实现并集操作

并集是求给定两个集合的一个合集，也就是所有元素组成的新集合

如何实现呢

  1. 首先我们需要接收一个传入的集合 otherSet ，并创建一个新的集合用来存放最后的数据
  2. 通过 values 方法展开集合成数组，遍历添加到新的集合中，对传入的数组也是如此
  3. 最后返回新集合
    注意噢，由于我们对 values 封装的时候，没有预留参数，因此我们在转化 otherSet 的时候需要使用 otherSet.values
  1. union(otherSet) {
  2.     const unionSet = new Set()
  3.     // 集合->数组
  4.     const values = this.values()
  5.     const values2 = otherSet.values(otherSet)
  6.     values.map(item => { unionSet.add(item) })
  7.     values2.map(item => { unionSet.add(item) })
  8.     return unionSet
  9. }

如何使用呢？

  1. const set = new Set()
  2. const set2 = new Set()
  3. set2.add(3)
  4. set.add(2)
  5. console.log(set.union(set2)); // Set { data: { '2': '2', '3': '3' } }

2. 实现交集操作

交集操作也就是：返回两个集合中的相同元素组成的新集合

实现思路

  1. 新建一个需要返回的集合，同时接收一个集合
  2. 同样的转化为数组来进行操作
  3. 取一个集合来遍历，拿到的元素在另一个集合中用 has 来判断，另一个集合中有没有这个值，有的话说明是公共存在的，添加到新的集合中
    你知道这样实现的时间复杂度是多少吗？
  1. intersection() {
  2.     const intersectionSet = new Set()
  3.     // 当前集合转化成数组
  4.     const values = this.values()
  5.     for (let i = 0; i < values.length; i++) {
  6.         if (otherSet.has(values[i])) {
  7.             intersectionSet.add(values[i])
  8.         }
  9.     }
  10.     return intersectionSet

3. 实现差集操作

差集操作就是返回相对不同的部分，A 和 B 的差集就是 A 单独的部分

蓝色这块就是我们要求的

实现思路，和求并集相反即可

  1. difference(otherSet) {
  2.     const differenceSet = new Set()
  3.     const values = this.values
  4.     for (let i = 0; i < values.length; i++) {
  5.         // 判断otherSet中有没有这个元素，没有就是相差的部分
  6.         if (!otherSet.has(values[i])) {
  7.             differenceSet.add(values[i])
  8.         }
  9.     }
  10.     return differenceSet
  11. }

4. 实现 subset 方法

subset 是用来判断它们是不是父子关系，也就是 A 集合是不是包含在 B 集合中

实现思路

  • 如果 A 集合大小大于 B 集合，则不可能是子集
  • 判断集合 A 中的所有元素是不是在集合 B 中都能找到
  1. subset(otherSet) {
  2.     if (this.size() > otherSet.size()) {
  3.         return false
  4.     }
  5.     // return 中断
  6.     let values = this.values()
  7.     for(let i = 0;i<values.length;i++) {
  8.         if(!otherSet.has(values[i])) {
  9.             return false
  10.         }
  11.     }
  12.     return true
  13. }

到现在！终于实现完了这些方法，其实思路都差不多，非常感谢能看到这里，谢谢~

五、LeetCode 实战

349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

在 LeetCode 刷题的时候，我们不需要自己实现一个集合，我们可以直接使用现成的 Set 类来创建一个集合

AC 优雅代码

  1. var intersection = function (nums1, nums2) {
  2.     // 对 nums1 去重
  3.     const set1 = new Set(nums1)
  4.     const set2 = new Set(nums2)
  5.     return [...new Set([...set1].filter(item => set2.has(item)))]
  6. };

可能和前面讲的使用的方法不一样，这是因为数组中有大量的 API 供我们使用，应对不同的场景我们需要能够做出选择

📖 总结

在这篇文章中我们封装了一个集合，同时实现了很多集合的操作方法。

在 ES6 中新增了 Set 类，它的底层是通过 map 来实现的，map 底层利用了哈希表来实现，它极大的优化了我们查值的速度，因此在刷题的时候，可以想想能不能使用 Set 来实现。

本文关于集合的内容就到这里结束了，相信你一定能从中学到很多东西。下一篇文章将带你探索字典的奥秘。

欢迎大家关注本专栏，持续关注最新文章~

本专栏的其他内容

从这里开始 👉 【化解数据结构】从这里开启数据结构和算法

栈 👉 【化解数据结构】什么是栈？手写实现一个栈结构!

队列 👉【化解数据结构】详解队列，优先队列，循环队列，并实现一个队列
最后，可能在很多地方讲诉的不够清晰，请见谅

💌 如果文章有什么错误的地方，或者有什么疑问，欢迎留言，也欢迎私信交流

版权说明 : 本文为转载文章, 版权归原作者所有 版权申明

原文链接 : https://linjc.blog.csdn.net/article/details/121469241

内容来源于网络，如有侵权，请联系作者删除！

数据结构leetcodeJavaScriptreact前端化解数据结构

相关文章

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新文章

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com