第七章 集合

說明

是由一組無序且唯一（即不能重復）的項組成的,以[值，值]的形式存盤元素，這個資料結構使用了與有限集合相同的數學概念，但應用在計算機科學的資料結構中，

運算

集合有并集,交集,差集,子集這幾種運算
并集：對于給定的兩個集合，回傳一個包含兩個集合中所有元素的新集合，

交集：對于給定的兩個集合，回傳一個包含兩個集合中共有元素的新集合，

差集：對于給定的兩個集合，回傳一個包含所有存在于第一個集合且不存在于第二個集合的元素的新集合，

子集：驗證一個給定集合是否是另一集合的子集，

簡單圖解

一個集合的基本方法

• add(value) : 添加一個(或幾個)新元素到堆疊頂
• delete(value) : 彈出堆疊頂元素,并回傳
• has(value) : 獲取堆疊頂元素
• values() : 回傳一個包含集合中所有值的陣列，
• isEmpty() : 判斷堆疊中是否有元素
• clear() : 移除集合中的所有元素
• size() : 回傳集合的元素個數
• union() : 并集
• intersection() : 交集
• difference() : 差集
• isSubsetOf() : 子集

集合實作

export default class Set<T> {
    items: any;
    count: number;

    constructor() {
        this.items = {};
        this.count = 0;
    }

    /**
     * 判斷是否有這個元素
     * @param element
     */
    has(element: any) {
        return Object.prototype.hasOwnProperty.call(this.items, element)
    }


    /**
     * 添加一個元素到物件中
     * 如果有就回傳false,無就添加并回傳true
     * @param element
     */
    add(element: T) {
        if (this.has(element)) {
            return false;
        }
        //將元素添加到集合中
        this.items[element] = element;
        //記得維護個數
        this.count++;
        return true;
    }

    /**
     * 洗掉集合中的一個元素
     * 如果沒有就回傳false,有就洗掉并回傳true
     * @param element
     */
    delete(element: T) {
        if (this.has(element)) {
            delete this.items[element];
            //記得維護個數
            this.count--;
            return true;
        }
        return false;
    }

    /**
     * 以陣列的形式回傳集合中的所有元素
     */
    values() {
        let result = [];
        let items = this.items;
        for (const key in items) {
            result.push(items[key])
        }
        return result;
    }

    /**
     * 回傳集合大小
     */
    size() {
        return this.count;
    }

    /**
     * 是否有元素
     */
    isEmpty() {
        return this.count === 0;
    }

    /**
     * 清空集合
     */
    clear() {
        this.items = {};
        this.count = 0;
    }

    /**
     * 并集
     * 這里可以利用add不會重復的性質
     * @param set
     */
    union(set: Set<T>) {
        let unionSet = new Set<T>();
        this.values().forEach((value) => {
            unionSet.add(value);
        })
        set.values().forEach((value) => {
            unionSet.add(value);
        })
        return unionSet;
    }

    /**
     * 交集
     * @param set
     */
    intersection(set: Set<T>) {
        let intersectionSet = new Set<T>();
        let lowSet = this.values();
        lowSet.forEach((val) => {
            if (set.has(val)) {
                intersectionSet.add(val);
            }
        })
        return intersectionSet;
    }

    /**
     * 差集
     * 當前集合中 包含  傳入集合  不存在的元素
     * @param set
     */
    difference(set: Set<T>) {
        let differenceSet = new Set<T>();
        this.values().forEach((val) => {
            if (!set.has(val)) {
                differenceSet.add(val);
            }
        })
        return differenceSet;
    }

    /**
     * 子集
     * 當前集合是否為傳入的集合的子集
     * @param set
     */
    isSubsetOf(set: Set<T>) {
        //當前集合小于傳入集合
        if(this.count > set.count){
            return false;
        }
        //如果當前集合中的值都在傳入的集合中,那么就說明是子集
        for (let i = 0,values = this.values(), len = values.length; i < len; i++) {
            if (!set.has(values[i])) {
                return false;
            }
        }

        return true;
    }


    toString() {
        if (this.isEmpty()) {
            return '';
        }
        const values = this.values();
        let objString = `${values[0]}`;
        for (let i = 1; i < values.length; i++) {
            objString = `${objString},${values[i].toString()}`;
        }
        return objString;
    }
} 

書中代碼

export default class Set<T> {
  private items: any;

  constructor() {
    this.items = {};
  }

  add(element: T) {
    if (!this.has(element)) {
      this.items[element] = element;
      return true;
    }
    return false;
  }

  delete(element: T) {
    if (this.has(element)) {
      delete this.items[element];
      return true;
    }
    return false;
  }

  has(element: T) {
    // return this.items.hasOwnProperty(element);
    return Object.prototype.hasOwnProperty.call(this.items, element);
  }

  values(): T[] {
    return Object.values(this.items);
  }

  union(otherSet: Set<T>) {
    const unionSet = new Set<T>();

    this.values().forEach(value =https://www.cnblogs.com/wangzhaoyv/archive/2020/11/15/> unionSet.add(value));
    otherSet.values().forEach(value => unionSet.add(value));

    return unionSet;
  }

  intersection(otherSet: Set) {
    const intersectionSet = new Set();

    const values = this.values();
    const otherValues = otherSet.values();

    let biggerSet = values;
    let smallerSet = otherValues;

    if (otherValues.length - values.length > 0) {
      biggerSet = otherValues;
      smallerSet = values;
    }

    smallerSet.forEach(value => {
      if (biggerSet.includes(value)) {
        intersectionSet.add(value);
      }
    });

    return intersectionSet;
  }

  difference(otherSet: Set) {
    const differenceSet = new Set();

    this.values().forEach(value => {
      if (!otherSet.has(value)) {
        differenceSet.add(value);
      }
    });

    return differenceSet;
  }

  isSubsetOf(otherSet: Set) {
    if (this.size() > otherSet.size()) {
      return false;
    }

    let isSubset = true;
    this.values().every(value => {
      if (!otherSet.has(value)) {
        isSubset = false;
        return false;
      }
      return true;
    });

    return isSubset;
  }

  isEmpty() {
    return this.size() === 0;
  }

  size() {
    return Object.keys(this.items).length;
  }

  clear() {
    this.items = {};
  }

  toString() {
    if (this.isEmpty()) {
      return'';
    }
    const values = this.values();
    let objString = `${values[0]}`;
    for (let i = 1; i < values.length; i++) {
      objString = `${objString},${values[i].toString()}`;
    }
    return objString;
  }
}

leetcode對應訓練

標籤：其他

上一篇：第六章 鏈表

下一篇：第八章 字典