首页

集合的概念和用途

# 集合的概念和用途

  • 集合是一种包含不同元素的数据结构。

  • 在很多编程语言中并不把集合当成一种数据类型，当你想要创建一个数据结构，用来保存一段独一无二的文字的时候，集合就非常有用。

  • 集合的成员是无序的。

  • 集合中不允许相同成员存在。

# 集合的一些关键点

  • 集合是一组无序但彼此间又有一定相关性的成员构成的，集合中的元素称为成员。

  • 不包含任何成员的集合称为空集。全集则是包含一切可能成员的集合。

  • 如果两个集合的成员完全相同，则称两个集合相等。

  • 如果一个集合中的所有成员都属于另外一个集合，则前一集合称为后一集合的子集。

  • 并集：将两个集合中的成员进行合并，得到一个新集合。

  • 交集：两个集合中共同存在的成员组成一个新的集合。

  • 差集：属于一个集合但不属于另一个集合的成员组成的集合。

# 集合的代码实现

function Set() {
  this.dataStore = [];
  this.add = add;
  this.remove = remove;
  this.has = has;
  this.size = size;
  this.show = show;
  this.union = union;
  this.intersect = intersect;
  this.difference = difference;
  this.subSet = subSet;
}

// 向集合中添加元素
function add(data) {
  if (!this.has(data)) {
    this.dataStore.push(data);
  }
}

// 删除集合中的元素
function remove(data) {
  var pos = this.dataStore.indexOf(data);
  if (pos !== -1) {
    this.dataStore.splice(pos, 1);
  }
}

// 判断集合中是否有某个元素
function has(data) {
  return this.dataStore.indexOf(data) > -1;
}

// 求集合中元素个数
function size() {
  return this.dataStore.length;
}

// 展示整个集合内容
function show() {
  return this.dataStore;
}

// 求并集
function union(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    tempSet.add(this.dataStore[i]);
  }
  for (var i = 0; i < set.dataStore.length; i++) {
    if (!tempSet.has(set.dataStore[i])) {
      tempSet.add(set.dataStore[i]);
    }
  }
  return tempSet;
}

// 求交集
function intersect(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (set.has(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}

// 求差集
function difference(set) {
  var tempSet = new Set();
  for (var i = 0; i < this.dataStore.length; i++) {
    if (!set.has(this.dataStore[i])) {
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}

// 判断一个集合是否是另一个集合的子集
function subSet(set) {
  if (set.size() > this.size()) {
    return false;
  } else {
    for (var i = 0; i < set.dataStore.length; i++) {
      if (!this.has(set.dataStore[i])) {
        return false;
      }
    }
    return true;
  }
}

var set = new Set();
set.add("first");
set.add("second");
set.add("third");
// set.remove('first');
var set1 = new Set();
set1.add("first");
set1.add("second");
set1.add("fourth");
console.log(set.show());
console.log("并集：", set.union(set1).show());
console.log("交集：", set.intersect(set1).show());
console.log("差集：", set.difference(set1).show());
var set2 = new Set();
set1.add("first");
set1.add("second");
console.log("是否是子集：", set.subSet(set2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110

# 集合的另一种实现

var Set = function() {
  var items = {};

  // has 检查元素是否存在
  this.has = function(value) {
    return items.hasOwnProperty(value);
  };

  // add 添加元素，要注意集合具有不重复性
  this.add = function(value) {
    if (!this.has(value)) {
      // 对象有两种访问方式：点语法和方括号语法，点语法后面的键不能是变量，只能是对象名；但是方括号语法可以是变量
      items[value] = value;
      return value;
    }
    return false;
  };

  // 移除元素
  this.remove = function(value) {
    if (this.has(value)) {
      delete items[value];
      return true;
    } else {
      return false;
    }
  };

  // 清空集合
  this.clear = function() {
    items = {};
  };

  // 获取集合的大小
  this.size = function() {
    // 遍历集合
    // var count = 0;
    // for(var i in items){
    //     if(items.hasOwnProperty(i)){     // 判断对象是否包含特定的自身属性（非继承）
    //         count++;
    //     }
    // }
    // return count;

    return Object.keys(items).length; // 静态方法Object.keys()返回的是一个数组，数组里的元素是键名，es6提出来的
  };

  // 提取集合的全部值并以数组形式返回
  this.value = function() {
    var values = [];
    for (var i in items) {
      if (items.hasOwnProperty(i)) {
        values.push(items[i]);
      }
    }
    return values;
  };

  // 并集
  this.union = function(otherSet) {
    var resultSet = new Set();

    // 把自己的值提取出来
    var arr = this.value();
    for (var i = 0; i < arr.length; i++) {
      resultSet.add(arr[i]);
    }

    // 把另一个集合的值提取出来
    arr = otherSet.value();
    for (var i = 0; i < arr.length; i++) {
      resultSet.add(arr[i]);
    }
    return resultSet;
  };

  // 交集
  this.intersection = function(otherSet) {
    var resultSet = new Set();

    // 把自己的值提取出来
    var arr = this.value();
    for (var i = 0; i < arr.length; i++) {
      if (otherSet.has(arr[i])) {
        resultSet.add(arr[i]);
      }
    }
    return resultSet;
  };

  // 差集
  this.difference = function(otherSet) {
    var resultSet = new Set();
    var arr = this.value();
    for (var i = 0; i < arr.length; i++) {
      if (!otherSet.has(arr[i])) {
        resultSet.add(arr[i]);
      }
    }
    return resultSet;
  };

  // 获取整个集合
  this.getItems = function() {
    return items;
  };
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107

# HashMap、TreeMap、HashSet、TreeSet

  • Hash 和 Binary Search Tree 是 Map 和 Set 底层实现的两种方式。

  • HashMap 和 HashSet 效率更快，但是元素是乱序的；而 TreeMap 和 TreeSet 效率相对慢一点，但是元素是有序的。所以具体使用哪种要看具体的需求场景。

# 两数之和 ✅

题目地址 (opens new window)

// 时间和空间复杂度都是 O(n)
var twoSum = function(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (map.has(diff)) {
      return [map.get(diff), i];
    }
    map.set(nums[i], i);
  }
  return [];
};
1
2
3
4
5
6
7
8
9
10
11
12

# 两个数组的交集 ✅

题目地址 (opens new window)

// 两个集合，时间和空间复杂度都是 O(m+n)
var intersection = function(nums1, nums2) {
  const set1 = new Set(nums1);
  const res = [];
  for (const num of nums2) {
    if (set1.has(num)) {
      res.push(num);
      set1.delete(num);
    }
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
// 排序+双指针，时间复杂度是 O(mlogm+nlogn)，空间复杂度是 O(logm+logn)
var intersection = function(nums1, nums2) {
  nums1.sort((a, b) => a - b);
  nums2.sort((a, b) => a - b);
  const len1 = nums1.length;
  const len2 = nums2.length;
  const res = [];
  let i = 0;
  let j = 0;
  while (i < len1 && j < len2) {
    if (nums1[i] === nums2[j]) {
      if (!res.includes(nums1[i])) {
        res.push(nums1[i]);
      }
      i++;
      j++;
    } else if (nums1[i] < nums2[j]) {
      i++;
    } else {
      j++;
    }
  }
  return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 赎金信

题目地址 (opens new window)

var canConstruct = function(ransomNote, magazine) {
  if (ransomNote.length > magazine.length) {
    return false;
  }

  const charArr = new Array(26).fill(0);
  const baseCharCode = "a".charCodeAt();

  for (const c of magazine) {
    charArr[c.charCodeAt() - baseCharCode]++;
  }
  for (const c of ransomNote) {
    charArr[c.charCodeAt() - baseCharCode]--;
    if (charArr[c.charCodeAt() - baseCharCode] < 0) {
      return false;
    }
  }

  return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 有效的字母异位词

题目地址 (opens new window)

方法一：可以直接将两个字符串中的字符进行排序，然后比较排序后的结果是不是完全一样。时间复杂度为：O(nlogn)。

var isAnagram = function(s, t) {
  return (
    s.length === t.length && [...s].sort().join("") === [...t].sort().join("")
  );
};
1
2
3
4
5

方法二：使用 map 来存储两个字符串中每个字符的出现的次数，然后比较这两个 map 是否一致。时间复杂度为：O(n)。

方法三：使用哈希表，思路跟使用 map 类似，维护一个长度为 26 的数组，先遍历记录字符串 s 中每个字符出现的次数，然后在遍历字符串 t，减去数组中相应字符的次数。遍历结束后，如果数组中有某一位次数不为 0，说明两者不一致，返回 false。时间复杂度为：O(n)。

charCodeAt 和 codePointAt 的作用都是获取字符的 Unicode 编码值，区别就是前者只能处理 16 位二进制数 0xffff 以内的值，而后者能正确处理到 32 位二进制数。

var isAnagram = function(s, t) {
  if (s.length !== t.length) {
    return false;
  }

  const arr = new Array(26).fill(0);
  const baseCodePoint = "a".codePointAt(0);

  for (let i = 0; i < s.length; i++) {
    arr[s.codePointAt(i) - baseCodePoint]++;
  }
  for (let i = 0; i < t.length; i++) {
    arr[t.codePointAt(i) - baseCodePoint]--;
    if (arr[t.codePointAt(i) - baseCodePoint] < 0) {
      return false;
    }
  }

  return true;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# 字母异位词分组

题目地址 (opens new window)

// 由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键
var groupAnagrams = function(strs) {
  const map = new Map();
  for (const str of strs) {
    const arr = Array.from(str);
    arr.sort();
    const key = arr.toString();
    const value = map.get(key) ? map.get(key) : [];
    value.push(str);
    map.set(key, value);
  }
  return Array.from(map.values());
};
1
2
3
4
5
6
7
8
9
10
11
12
13

# 存在重复元素

题目地址 (opens new window)

var containsDuplicate = function(nums) {
  const set = new Set();
  for (let i = 0; i < nums.length; i++) {
    if (set.has(nums[i])) {
      return true;
    }
    set.add(nums[i]);
  }
  return false;
};
1
2
3
4
5
6
7
8
9
10
// 另一种解法，先排序，排序后重复的元素肯定位于相邻的位置
var containsDuplicate = function(nums) {
  nums.sort((a, b) => a - b);
  for (let i = 0; i < nums.length - 1; i++) {
    if (nums[i] === nums[i + 1]) {
      return true;
    }
  }
  return false;
};
1
2
3
4
5
6
7
8
9
10

# 缺失的第一个正数

题目地址 (opens new window)

// 将给定的数组设计成哈希表，将所有在 [1,N] 范围内的数放入哈希表
var firstMissingPositive = function(nums) {
  const n = nums.length;
  // 将数组中小于等于 0 的数修改成任意一个大于 n 的数，比如 n + 1
  // 这样一来，数组中的所有数就都是正数了，方便后续将「标记」表示为「负号」
  for (let i = 0; i < n; i++) {
    if (nums[i] <= 0) {
      nums[i] = n + 1;
    }
  }
  // 遍历数组中的每一个数 x，它可能已经被打了标记，因此原本对应的数为 ∣x∣
  // 如果 |x|∈[1, n]，那么我们给数组中的第 ∣x∣−1 个位置的数添加一个负号
  // 如果它已经有负号，不需要重复添加
  for (let i = 0; i < n; i++) {
    const x = Math.abs(nums[i]);
    if (x >= 1 && x <= n) {
      nums[x - 1] = nums[x - 1] < 0 ? nums[x - 1] : -nums[x - 1];
    }
  }
  // 上面的工作做完之后，如果数组中的每一个数都是负数，那么答案是 N+1，否则答案是第一个正数的位置加 1
  for (let i = 0; i < n; i++) {
    if (nums[i] > 0) {
      return i + 1;
    }
  }
  return n + 1;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

# LRU 缓存

题目地址 (opens new window)

var LRUCache = function(capacity) {
  this.map = new Map();
  this.capacity = capacity;
};

LRUCache.prototype.get = function(key) {
  if (!this.map.has(key)) {
    return -1;
  }
  const value = this.map.get(key);
  this.map.delete(key);
  this.map.set(key, value);
  return value;
};

LRUCache.prototype.put = function(key, value) {
  if (this.map.has(key)) {
    this.map.delete(key);
  }
  this.map.set(key, value);
  if (this.map.size > this.capacity) {
    this.map.delete(this.map.keys().next().value);
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 单词替换

题目地址 (opens new window)

var replaceWords = function(dictionary, sentence) {
  const set = new Set();
  for (const root of dictionary) {
    set.add(root);
  }
  const words = sentence.split(" ");
  for (let i = 0; i < words.length; i++) {
    const word = words[i];
    for (let j = 0; j < word.length; j++) {
      if (set.has(word.substring(0, j + 1))) {
        words[i] = word.substring(0, j + 1);
        break;
      }
    }
  }
  return words.join(" ");
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
上次更新时间: 2026年06月12日 14:55:18

散列