前端必会数据结构与算法系列之集合与字典-一一网

1. 什么是集合

由一组无序且唯一（即不能重复）的项组成的
可以把集合想象成一个既没有重复元素，也没有顺序概念的数组

常用操作：

去重
判断某元素是否在集合中
求交集/差集/并集

// 去重
const arr = [1, 1, 2, 2];
const arr2 = [...new Set(arr)];

// 判断元素是否在集合中
const set = new Set(arr);
const has = set.has(3);

// 求交集
const set2 = new Set([2, 3]);
const set3 = new Set([...set].filter(item => set2.has(item)));
复制代码

2. 实现一个集合

add(element)：向集合添加一个新元素。
delete(element)：从集合移除一个元素。
has(element)：如果元素在集合中，返回 true，否则返回 false。
clear()：移除集合中的所有元素。
size()：返回集合所包含元素的数量。它与数组的 length 属性类似。
values()：返回一个包含集合中所有值（元素）的数组。

class Set {
    constructor () {
        this.items = {}
    }

    has (element) {
        return Object.prototype.hasOwnProperty.call(this.items, element)
    }

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

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

    clear () {
        this.items = {}
    }

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

    values () {
        return Object.values(this.items)
    }
}
复制代码

3. 集合运算

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

3.1 求并集

let union = a.concat(b.filter(v => !a.includes(v)))

new Set([...setA, ...setB])
复制代码

3.2 求交集

解题思路：求交集且无序唯一。

解题步骤：

1. 用集合对num1去重
1. 遍历nums1,筛选出nums2也包含的值

时间复杂度filter+includesO(m*n), 空间复杂度O(m)

var intersection = function(nums1, nums2) {
    return [...new Set(nums1)].filter(n => nums2.includes(n))
};
复制代码

3.3 求差集

let difference = a.concat(b).filter(v => a.includes(v) && !b.includes(v))
new Set([...setA].filter(x => !setB.has(x)))
复制代码

3.4 求子集

var intersection = function(nums1, nums2) {
    if (nums2.length < nums1.length) {
        return false
    }

    return nums1.every(value => {
        return nums2.include(value)
    })
}
复制代码

4. 什么是字典

字典和集合很相似，集合以[值，值]的形式存储元素，字典则是以[键，值]的形式来存储元素。字典也称作映射、符号表或关联数组。js中字典由散列表实现。

5. 实现一个字典

defaultToString(item) {
  if (item === null) {
    return 'NULL';
  } if (item === undefined) {
    return 'UNDEFINED';
  } if (typeof item === 'string' || item instanceof String) {
    return `${item}`;
  }
  return item.toString();
}

class ValuePair {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }

  toString() {
    return `[#${this.key}: ${this.value}]`;
  }
}

class Dictionary {
    constructor(toStrFn = defaultToString) {
        this.toStrFn = toStrFn;
        this.table = {};
    }

    set(key, value) {
        if (key != null && value != null) {
            const tableKey = this.toStrFn(key);
            this.table[tableKey] = new ValuePair(key, value);
            return true;
        }
        return false;
    }

    get(key) {
        const valuePair = this.table[this.toStrFn(key)];
        return valuePair == null ? undefined : valuePair.value;
    }

    hasKey(key) {
        return this.table[this.toStrFn(key)] != null;
    }

    remove(key) {
        if (this.hasKey(key)) {
            delete this.table[this.toStrFn(key)];
            return true;
        }
        return false;
    }

    values() {
        return this.keyValues().map(valuePair => valuePair.value);
    }

    keys() {
        return this.keyValues().map(valuePair => valuePair.key);
    }

    keyValues() {
        return Object.values(this.table);
    }

    forEach(callbackFn) {
        const valuePairs = this.keyValues();
        for (let i = 0; i < valuePairs.length; i++) {
            const result = callbackFn(valuePairs[i].key, valuePairs[i].value);
            if (result === false) {
                break;
            }
        }
    }

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

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

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

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

JAVA set实现：docs.oracle.com/en/java/jav…
JAVA map实现：docs.oracle.com/en/java/jav…

6. 字典常用操作

6.1 求交集

解题思路：

1. 求nums1和nums2都有的值。
1. 用字典建立一个映射关系，记录nums1里有的值。

时间复杂度O(m+n), 空间复杂度：O(m)

解题步骤：

1. 新建一个字典，遍历nums1，填充字典
1. 遍历nums2,遇到字典里的值就选出，并从字典中删除

var intersection = function(nums1, nums2) {
    const map = new Map();
    nums1.forEach(n => {
        map.set(n, true)
    })
    const res = []
    nums2.forEach(n => {
        if(map.get(n)){
            res.push(n)
            map.delete(n)
        }
    })
    return res;
}
复制代码