iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 7
3

我想大家跟我一樣上一次聽到集合是高中的數學課上...,就在這篇文章來複習一下
https://ithelp.ithome.com.tw/upload/images/20190908/20106426U9RYlFqWgN.jpg

什麼是集合?

一組無順序且不重複的元素組成

這三個集合是相同的 
{2, 4} , {4, 2}, {2, 4, 4, 2} 

想知道更精確的解釋可以看維基百科

來建立集合吧

其實 ES6 有原生的 Set 可以用,但為了加強自己印象,就先用 javaScript Object 模擬 Set (使用 Object 好處是 Object key 是唯一)

// -------------------------------------
// Before add and remove have to check 
// the element already exist in current Set
// -------------------------------------
class MySet {
    constructor(){
        this.items = {};
    }   
    // 新增
    add(value) {
        if(!this.has(value)){
            this.items[value] = value;
        }
    };
    // 刪除
    delete(value) {
        if(this.has(value)){
           delete this.items[value];
           return true;
        }
        return false;
    };
    // 判斷元素存不存在
    has(value) {
        return this.items.hasOwnProperty(value);
    };
    // 清掉集合所有元素
    clear() {
       this.items = {};
    };
    // 此集合裡有幾個元素
    size() {
       return Object.keys(this.items).length
    };
    // 印出所有集合元素
    // print all values
    values() {
       return Object.values(this.items)
    };
}
    
let instruments = new MySet();
    
instruments.add('piano');
instruments.has('guitar');
instruments.add('guitar');
instruments.add('drum');
instruments.delete('guitar');
newSet.size(); // 2
newSet.values(); //['piano', 'drum']

以下是 ES6 原生寫法

// ES6 Set
let instruments = new Set();

instruments.add('piano');
instruments.has('guitar'); // false
instruments.add('drum');
instruments.delete('guitar'); // 裡面根本沒有 guitar 所以回傳 false
instruments.size; // 2
[...instruments] //['piano', 'drum']

// or use Array.from, 
Array.from(instruments); 

當然你要一開始就把值存進去也可以

// ES6 Set
let instruments = new Set(['piano', 'guitar', 'drum',]); // 記得是 Array 格式

instruments.has('guitar'); // true
instruments.add('drum'); // 是不會加進去的喔
instruments.delete('guitar');
instruments.size; // 2
[...instruments2] //['piano', 'drum']

集合操作

知道集合的基本方法後,就可以開始來操作集合了

Union 聯集

給兩個集合,回傳一個包含兩個集合中元素的新集合
https://ithelp.ithome.com.tw/upload/images/20190908/20106426BRaImSWOid.jpg

const union = (firstSet, otherSet) => {
    // store union, use es6 Spread syntax
    return new Set([...firstSet, ...otherSet]); 
}

// 範例一
let a = new Set([1, 2, 3])
let b = new Set([2, 3, 4, 5, 6])
union(a, b); // 1, 2, 3, 4, 5, 6

// 範例二
let c = new Set();
c.add(1);
c.add(2);
c.add(3);
let d = new Set([1, 2, 3])
union(a, b); // {1, 2, 3, 4, 5, 6}

Intersection 交集

給兩個集合,回傳兩個集合中共同有的元素
https://ithelp.ithome.com.tw/upload/images/20190908/20106426fd10yqtxzv.jpg

const intersection = (firstSet, otherSet) => {
    // store intersectionSet 
    let intersectionSet = new Set();
    firstSet.forEach(i => {
        if(otherSet.has(i) == true){
            intersectionSet.add(i)
        }
    })
    // get the same value
    return intersectionSet;   
}
// 範例
let a = new Set([1, 2, 3])
let b = new Set([2, 3, 4, 5, 6])
intersection(a, b); // {2, 3}

Symmetric Difference 對稱差

給定兩集合,回傳兩個集合的元素但不包含重覆元素
https://ithelp.ithome.com.tw/upload/images/20190908/20106426evjcR40bkx.jpg

// 運用 union 跟 intersection 達成對稱差
const difference = (firstSet, otherSet) => {
    // store union
    let differenceSet = union(firstSet, otherSet);
    let intersectionSet = intersection(firstSet, otherSet);
    differenceSet.forEach(i => {
        if(intersectionSet.has(i) == true){
            differenceSet.delete(i)
        }
    })
    
    return differenceSet;   
}
// 範例
let a = new Set([1, 2, 3])
let b = new Set([2, 3, 4, 5, 6])
difference(a, b); // {1, 4, 5, 6}

Subtraction 差集

給定兩集合,回傳一個包含存在第一個集合元素但不存在於第二集合的集合
https://ithelp.ithome.com.tw/upload/images/20190908/20106426c5XZZz0VMk.jpg

const subtracting = (firstSet, otherSet) => {
    let subtractingSet = new Set([...firstSet]);
    otherSet.forEach(i => {
        if(subtractingSet.has(i) == true){
            subtractingSet.delete(i)
        }
    })
    return subtractingSet;
}

// 範例
let a = new Set([1, 2, 3])
let b = new Set([2, 3, 4, 5, 6])
console.log(subtracting(a, b)); // {1}

要看更多原生 Set 屬性可以看這裡。LeetCode 中有許多題目用 Set 來寫效能可以更好。在練習 Set 相關 LeetCode 之前,明天會先來討論 Array 跟 Set 的不同

如有錯誤或需要改進的地方,拜託跟我說。
我會以最快速度修改,感謝您

上一篇
[LeetCode #905, #561] Array
下一篇
Array vs. Set
系列文
前端工程師用 javaScript 學演算法32

2 則留言

0
海綿寶寶
iT邦超人 1 級 ‧ 2019-09-08 15:48:43

我想大家跟我一樣上一次聽到集合是高中的數學課上

不,我是在旅行團的遊覽車前面
/images/emoticon/emoticon48.gif

0
hyj1116
iT邦新手 4 級 ‧ 2019-09-08 23:52:55

“Symmetric Difference 對稱差” 跟 ”Subtraction 差集“ 的文字描述好像重複了?

感謝糾正,改好了~

奇怪用手機回覆都會自己生兩個重覆留言...

我要留言

立即登入留言