专栏首页一Li小麦《javascript数据结构和算法》读书笔记(5):集合

《javascript数据结构和算法》读书笔记(5):集合

第四讲 集合(items)

集合是一种不允许重复的数据结构(无序且唯一)。

{1,2,3,4}就是一个集合。 {}视为空集

创建一个集合(基于ES6的Set)

在创建时有一个细节,使用对象(items)而不是数组来创建集合。但使用数组的话意义似乎不大。

元素存在的键值对类似 'value':value

创建一个基于对象的集合,是之拥有以下方法:

  • add(value):在集合中添加新项
  • remove(value):从集合中移除一个值
  • has(value): 如果值在集合中,返回true,否则为false
  • clear():移除所有集合中的项目,返回空集
  • size:返回集合包含的元素个数
  • values:以数组形式返回集合元素列表
// 集合
class Set{
    constructor(){
        this.items={};
    }

    // 是否含有
    has(value){
        // return value in this.items;
        return this.items.hasOwnProperty(value)
    }

    // 添加
    add(value){
        if(!this.has(value)){
            this.items[value]=value;
        }
    }

    // 删除
    remove(value){
        if(this.has(value)){
            delete this.items[value];
            return true
        }
    }

    // 清理
    clear(){
        this.items={}
    }

    // 长度
    size(){
        // ES6中Obeject.key方法以数组形式返回对象的属性列表(IE9+)
        return Object.keys(this.items).length;
    }

    // 以数组形式返回所有值
    values(){
        let values=[];
        let keys=Object.keys(this.items);
        for(let i=0;i<keys.length;i++){
            values.push(this.items[keys[i]])
        }
        return values;
    }
}

来测试一下吧

// 测试用例
let a=new Set();
a.add('dangjingtao');
a.add('djtao')
console.log(a.has('taotao'))
a.add('taotao');
console.log(a.has('taotao'))
console.log(a.values())
a.remove('djtao')
console.log(a.size())

集合操作

高一数学补白

集合的数据类型精髓在于运算。在此补白如下

this is 交集

这是并集:

这是差集

并集(union)运算的实现

并集定义如下:

A B={x|x A V x B}

// 并集
    union(otheSet){
        let unionSet=new Set();
        let values=this.values();
        for(let i=0;i<values.length;i++){
            unionSet.add(values[i])
        }

        values=otherSet.values();
        for(let i=0;i<values.length;i++){
            unionSet.add(values[i])
        }

        return unionSet;
    }

测试用例:

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

let b = new Set();
b.add(3);
b.add(4);
b.add(5);

console.log(a.union(b))

注意,3只会1一次。

交集(intersection)的实现

A∩B={x|x A ^ x B}

交集的话,最好是去遍历其中一个,拿另一个去判断,就可以了、

// 交集
    intersection(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;
    }

测试用例:

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

let b = new Set();
b.add(3);
b.add(4);
b.add(5);

console.log(a.intersection(b))

差集(difference)实现

A-B={x|x A ^ x 不属于B}

思路是遍历A,找出不属于B的

// 差集
    difference(otherSet){
        let values=this.values();
        let set=new Set();

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

        return set;
    }

判断是否子集(subSet)

A包含于B

// 是否子集
    subSet(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;
                }
            }
        }
    }

ES6中的类

ECMA2015中,新增了Set类。

Set 对象允许你存储任何类型的唯一值,无论是[原始值)或者是对象引用。

语法

new Set([iterable]);

参数

  • iterable 如果传递一个可迭代对象,它的所有元素将不重复地被添加到新的 Set中。如果不指定此参数或其值为null,则新的 Set为空。

返回的事一个新的 Set对象。

const set = new Set([1, 2, 3, 4, 5]);

console.log(set.size)
//5

console.log(set.has(1));
// true

console.log(set.has(6));
// false

console.log(set.values());
// SetIterator { 1, 2, 3, 4, 5 }

values()方法返回的是一个SetIterator 对象。

原生Set支持的方法

  • Set.prototype.add(value)Set对象尾部添加一个元素。返回该``Set对象。
  • Set.prototype.clear() 移除 Set对象内的所有元素。
  • Set.prototype.delete(value) 移除Set的中与这个值相等的元素,返回Set.prototype.has(value)在这个操作前会返回的值(即如果该元素存在,返回true,否则返回false)。``Set.prototype.has(value)在此后会返回false。
  • Set.prototype.entries() 返回一个新的迭代器对象,该对象包含Set对象中的按插入顺序排列的 所有元素的值的[value,value]数组。为了使这个方法Map对象保持相似, 每个值的键和值相等。
  • Set.prototype.forEach(callbackFn[,thisArg\]) 按照插入顺序,为Set对象中的每一个值调用一次callBackFn。如果提供了 thisArg参数,回调中的this会是这个参数。
  • Set.prototype.has(value) 返回一个布尔值,表示该值在 Set中存在与否。
  • Set.prototype.keys()values() 方法相同,返回一个新的迭代器对象,该对象包含Set对象中的按插入顺序排列的 所有元素的值。
  • Set.prototype.values() 返回一个新的迭代器对象,该对象包含Set对象中的按插入顺序排列的 所有元素的值。
  • Set.prototype[@@iterator]() 返回一个新的迭代器对象,该对象包含Set对象中的按插入顺序排列的 所有元素的值。

我们说的迭代器对象 SetIterator。可以使用iterable内置的forEach方法 :

let set=new Set([1,2,3,4,5])
set.forEach((element, sameElement, set) => {
    console.log(element, sameElement, set)
});
// 1 1 Set { 1, 2, 3, 4, 5 }
// 2 2 Set { 1, 2, 3, 4, 5 }
// 3 3 Set { 1, 2, 3, 4, 5 }
// 4 4 Set { 1, 2, 3, 4, 5 }
// 5 5 Set { 1, 2, 3, 4, 5 }

使用举例:数组去重

ES6中 Array新增了一个静态方法 Array.from,可以把类似数组的对象转换为数组,如通过 querySelectAll方法得到 HTML DOMNodeList,以及ES6中新增的 SetMap等可遍历对象,

由此可以实现一行代码数组去重:

let array = Array.from(new Set([1, 1, 1, 2, 3, 2, 4]));
console.log(array);

对象语法的扩展

对象并没有实现集合运算。现在来扩展一下吧。

并集:

// 并集
Set.prototype.union = function (otherSet) {

    let unionSet = new Set();

    this.forEach((element, sameElement, set) => {
        // console.log(element, sameElement, set)
        unionSet.add(element)
    });

    otherSet.forEach((element, sameElement, set) => {
        // console.log(element, sameElement, set)
        unionSet.add(element)
    });
    return unionSet;
}



const set = new Set([1, 2, 3, 4, 5]);
let set2=new Set([1,2,6,7])
console.log(set.union(set2))//Set { 1, 2, 3, 4, 5, 6, 7 }

交集

// 并集
Set.prototype.intersection = function (otherSet) {

    let unionSet = new Set();

    this.forEach((element, sameElement, set) => {
        if(otherSet.has(element)){
            unionSet.add(element)
        }
    });

    return unionSet;
}



const set = new Set([1, 2, 3, 4, 5]);
let set2=new Set([1,2,6,7])
console.log(set.intersection(set2))//Set { 1, 2 }

差集

// 差集
Set.prototype.difference = function (otherSet) {

    let unionSet = new Set();

    this.forEach((element, sameElement, set) => {
        if(!otherSet.has(element)){
            unionSet.add(element)
        }
    });

    return unionSet;
}

本文分享自微信公众号 - 一Li小麦(gh_c88159ec1309),作者:一li小麦

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

原始发表时间:2019-04-15

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • hand first python 选读(1)

    结果pause解析不了。每一行做多一个判断。取反用的是 not方法,查找用的是 find方法。

    一粒小麦
  • 组件设计基础(2)

    早期的react设计了许多的生命周期钩子。它们严格定义了组件的生命周期,一般说,生命周期可能会经历如下三个过程:

    一粒小麦
  • Js算法与数据结构拾萃(1)

    算法是为了解决某些问题所提供的精确解法,数据结构是为了支撑算法提供的一种存储结构。

    一粒小麦
  • 资本寒冬却获赌王家族加持,创梦天地凭什么?

    游戏行业因为版号问题、增长瓶颈以及资本寒冬,在2018年迎来至暗时刻。日前,今年5月启动IPO的游戏公司创梦天地有了新消息,让充满寒意的游戏行业多了一丝暖意。

    罗超频道
  • 正则去除html字符串中的注释、标签、属性

    ProsperLee
  • docker学习(8) 在mac机上搭建私有仓库

    docker的私有仓库类似maven的私服,一般用于公司内部搭建一个类似docker hub的环境,这样上传、下载镜像速度较快,本文将演示如何在mac上利用do...

    菩提树下的杨过
  • android studio简单使用(B):代码模版快捷键Live Templates

    因为暂时还没有考虑好顺序,先用B表示 因为发现是很早写的,没有写完 先发布,以后有时间再添加吧

    dodo_lihao
  • 【正经说】尽职调查的2万字深度解析(含图文和模板)

    尽职调查简称尽调,又称谨慎性调查(Due Diligence ResponsibleInvestigation),是指投资人在与目标企业达成初步合作意向后,经协...

    辉哥
  • TypeScript

    TypeScript 是JavaScript类型的超集,它可以编译成纯JavaScript。

    余生
  • 回文词

    在本题中,每个字符的镜像如图所示(空白符表示该字符镜像之后不能得到一个合法字符)。

    Vincent-yuan

扫码关注云+社区

领取腾讯云代金券