05-28 15:14 已编辑广东技术师范大学运营发布于北京

关注

集合

集合的基本概念

在编程中，我们经常需要存储一些数据，同时希望这些数据是独一无二、没有重复的。

集合就是专门为这种需求而诞生的数据结构。它可以看作是一个特殊的容器，允许我们随意地把元素丢进去，但如果某个元素已经存在，集合会悄悄地帮我们忽略重复，保证集合里始终只保留独一份的数据。

这种机制非常适合去重、快速查找、集合操作等场景。

不同语言中的集合的底层实现略有不同，有的使用哈希表（如 Python 的 set，Java 的 HashSet），查找速度极快，平均只需 $O(1)$ 的时间；

有的则使用红黑树（如 C++ 的 set，Java 的 TreeSet），不仅能保证元素有序，还能支持前驱后继查询。

无论是哪种实现，Set 都帮我们省去了繁琐的重复判断，让代码更简洁高效。因此，每当你遇到需要"唯一性"或者"快速判断某元素是否存在"的问题时，第一个想到的，就应该是 Set。

常见特性：

元素不重复。
插入、删除、查找效率高。
自动去重。
在某些语言（如 C++、Java）中，可以保证元素有序。

集合的基本操作

集合（Set）支持如下基础操作：

功能语法（伪代码）单次操作时间复杂度举例

插入元素	`set.insert(x)`	$O(\log n)$	向集合中插入元素 3
删除元素	`set.erase(x)`	$O(\log n)$	删除集合中的元素 3
查找元素是否存在	`set.find(x)` / `x in set`	$O(\log n)$	查找元素 3 是否存在
查看集合大小	`set.size()`	$O(1)$	获取集合中元素数量
清空集合	`set.clear()`	$O(1)$	清空所有元素

默认数据类型的集合

C++

在 C++ 中，我们通常使用 STL 标准库中的 set 实现集合。其底层基于红黑树。

#include <bits/stdc++.h>
using namespace std;

int main() {
    set<int> s;

    s.insert(5);
    s.insert(3);
    s.insert(5); // 重复插入无效

    cout << "集合大小: " << s.size() << endl; // 输出: 2

    if (s.find(3) != s.end()) cout << "3 存在于集合中" << endl;

    s.erase(3);

    for (auto x : s) {
        cout << x << " ";
    }
    cout << endl; // 输出: 5

    return 0;
}

小细节

set 中元素自动有序（默认从小到大）。
不允许出现重复元素。如果向集合中插入一个已经存在于集合中的元素，插入操作将被忽略。

Java

在 Java 中，我们使用 HashSet 或 TreeSet：

HashSet：基于哈希表，无序， $O(1)$ 查找。
TreeSet：基于红黑树，有序， $O(\log n)$ 查找。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Set<Integer> set = new HashSet<>();

        set.add(5);
        set.add(3);
        set.add(5);

        System.out.println("集合大小: " + set.size()); // 输出: 2

        if (set.contains(3)) {
            System.out.println("3 存在于集合中");
        }

        set.remove(3);

        for (int num : set) {
            System.out.print(num + " ");
        }
    }
}

Python

Python 中内置了 set 类型，基于哈希表实现，插入、删除、查找平均时间复杂度为 $O(1)$ 。

# 创建一个空集合
s = set()

s.add(5)
s.add(3)
s.add(5)  # 重复插入无效

print(f"集合大小: {len(s)}") # 输出: 2

if 3 in s:
    print("3 存在于集合中")

s.remove(3)

for x in s:
    print(x, end=' ')

例题1：【模板】集合操作

思路分析

本题要求维护一个集合，支持如下操作：

插入一个元素。
删除一个元素。
查询一个元素是否存在。
查询集合大小。
查询一个元素的前驱。
查询一个元素的后继。

其中，前驱指的是集合中小于 x 的最大元素，后继指的是集合中大于 x 的最小元素。

使用 set<int> 容器即可方便地完成以上所有操作：

插入元素：set.insert(x)
删除元素：set.erase(x)
查询元素是否存在：set.find(x) != set.end()
集合大小：set.size()
查询前驱：
- set.lower_bound(x) 得到第一个大于等于 x的元素。
- 取 lower_bound(x) 的前一个迭代器，即是小于 x 的最大元素。
查询后继：
- set.upper_bound(x) 得到第一个大于 x的元素，即是后继。

特别注意：

如果查询前驱时 lower_bound(x) 指向 begin()，说明没有比 x 更小的数，应返回 -1。
如果查询后继时 upper_bound(x) 指向 end()，说明没有比 x 更大的数，应返回 -1。

代码实现

c++
java
python

#include<bits/stdc++.h>
using namespace std;

// 全局 set
set<int> s;

void insertValue(int x){
    s.insert(x);
}

void eraseValue(int x){
    s.erase(x);
}

int xInSet(int x){
    return s.find(x) != s.end();
}

int sizeOfSet(){
    return s.size();
}

int getPre(int x){
    auto it = s.lower_bound(x);
    if (it == s.begin()) return -1; // 没有更小的元素
    --it;
    return *it;
}

int getBack(int x){
    auto it = s.upper_bound(x);
    if (it == s.end()) return -1; // 没有更大的元素
    return *it;
}

int main(){
    int q, op, x;
    cin >> q;
    while (q--){
        cin >> op;
        if(op == 1){
            cin >> x;
            insertValue(x);
        }
        if(op == 2){
            cin >> x;
            eraseValue(x);
        }
        if(op == 3){
            cin >> x;
            if(xInSet(x)){
                cout << "YES\n";
            }else{
                cout << "NO\n";
            }
        }
        if(op == 4){
            cout << sizeOfSet() << endl;
        }
        if(op == 5){
            cin >> x;
            cout << getPre(x) << endl;
        }
        if(op == 6){
            cin >> x;
            cout << getBack(x) << endl;
        }
    }
    return 0;
}


import java.util.*;

public class Main {

    public static void main(String[] args) {
        // 使用 Scanner 读取标准输入
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();  // 操作总数

        // TreeSet 是基于红黑树的有序集合，支持快速的前驱/后继/大小/包含检查
        TreeSet<Integer> ts = new TreeSet<>();

        // 用 StringBuilder 累积输出，最后一次性打印
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int opt = in.nextInt();

            if (opt == 4) {
                // 操作 4：查询大小，直接返回 ts.size()
                sb.append(ts.size()).append('\n');
            } else {
                // 其他操作都需要一个参数 x
                int x = in.nextInt();
                switch (opt) {
                    case 1:
                        // 插入：若已存在自动忽略
                        ts.add(x);
                        break;
                    case 2:
                        // 删除：若不存在自动忽略
                        ts.remove(x);
                        break;
                    case 3:
                        // 存在性查询：contains 返回 boolean
                        sb.append(ts.contains(x) ? "YES" : "NO").append('\n');
                        break;
                    case 5:
                        // 前驱查询：lower(x) 返回严格小于 x 的最大元素，若无则 null
                        Integer pred = ts.lower(x);
                        sb.append(pred == null ? -1 : pred).append('\n');
                        break;
                    case 6:
                        // 后继查询：higher(x) 返回严格大于 x 的最小元素，若无则 null
                        Integer succ = ts.higher(x);
                        sb.append(succ == null ? -1 : succ).append('\n');
                        break;
                    default:
                        // 理论上不会出现的 opt 值，可视情况抛异常或忽略
                        break;
                }
            }
        }

        // 打印所有结果
        System.out.print(sb.toString());
        in.close();
    }
}

import sys
import bisect


def main():
    input = sys.stdin.readline
    n = int(input().strip())

    # 用于快速判断元素是否存在的哈希集合
    S = set()
    # 用于保持所有元素有序的列表，支持前驱/后继查找
    A = []

    # 将所有输出先收集到列表，最后一次性打印，减少 I/O 开销
    out = []

    for _ in range(n):
        parts = input().split()
        opt = int(parts[0])
        # 操作 4 没有 x 参数，其它操作都需要
        x = int(parts[1]) if len(parts) > 1 else None

        if opt == 1:
            # 插入操作：如果 x 不在集合中，则同时加入 S 与 A
            if x not in S:
                S.add(x)
                # bisect.insort 在有序列表中插入 x，保持列表有序
                bisect.insort(A, x)

        elif opt == 2:
            # 删除操作：如果 x 在集合中，则从 S 和 A 中删除
            if x in S:
                S.remove(x)
                # 在 A 中定位 x 的位置并弹出
                idx = bisect.bisect_left(A, x)
                A.pop(idx)

        elif opt == 3:
            # 存在性查询：如果 x 在 S 中输出 YES，否则 NO
            out.append('YES' if x in S else 'NO')

        elif opt == 4:
            # 大小查询：直接输出集合 S 的长度
            out.append(str(len(S)))

        elif opt == 5:
            # 前驱查询：在有序列表 A 中找到第一个 ≥ x 的位置 i
            # 它左侧的元素就是小于 x 的最大值
            i = bisect.bisect_left(A, x)
            if i == 0:
                # 如果 i==0，说明 A 中所有元素都 ≥ x，没有前驱
                out.append('-1')
            else:
                out.append(str(A[i-1]))

        elif opt == 6:
            # 后继查询：在有序列表 A 中找到第一个 > x 的位置 i
            # 它就是大于 x 的最小值
            i = bisect.bisect_right(A, x)
            if i == len(A):
                # 如果 i 越过末尾，说明没有后继
                out.append('-1')
            else:
                out.append(str(A[i]))

    # 一次性输出所有结果
    sys.stdout.write('\n'.join(out))


if __name__ == '__main__':
    main()

集合的遍历

在 C++ 中，可以用迭代器或者范围 for 循环遍历 Set：

set<int> s = {5, 2, 8};

for (auto it = s.begin(); it != s.end(); ++it) {
    cout << *it << " ";
}
cout << endl;

// 或者更简单的范围for
for (auto x : s) {
    cout << x << " ";
}

在 Java 中：

for (int num : set) {
    System.out.print(num + " ");
}

在 Python 中：

for x in s:
    print(x, end=" ")

多重集合

在普通的 set 中，每个元素只能出现一次，一旦插入了重复元素，集合会自动忽略。
但是，在很多实际应用中，我们希望能够记录元素的出现次数，而不仅仅是关注元素是否存在。

比如：

超市库存系统中，同一商品可以有多件库存；
游戏装备中，同一种材料可能采集到很多次；
统计投票时，可能有多个人投给了同一个选项。

在这些场景中，仅仅使用普通的 set 已经无法满足需求了，因为我们需要记录重复出现的元素。
这时，就需要使用multiset（多重集合）来解决问题。

C++ 中的多重集合

使用 std::multiset：

#include <bits/stdc++.h>
using namespace std;

int main() {
    multiset<int> ms;

    ms.insert(5);
    ms.insert(3);
    ms.insert(5);

    cout << "5 出现次数: " << ms.count(5) << endl;

    ms.erase(ms.find(5));  // 删除一个 5

    for (auto x : ms) {
        cout << x << " ";
    }
}

小结：

insert(x)：插入一个元素。
erase(find(x))：只删除一个元素（如果直接 erase(x)，会删除所有 x）。

Java 中的 Multiset

Java 标准库没有 Multiset，但可以用 Guava 的 HashMultiset：

import com.google.common.collect.HashMultiset;
import com.google.common.collect.Multiset;

Multiset<Integer> ms = HashMultiset.create();
ms.add(5);
ms.add(3);
ms.add(5);

System.out.println(ms.count(5)); // 输出: 2
ms.remove(5);
System.out.println(ms.count(5)); // 输出: 1

Python 中的 Multiset

使用 collections.Counter：

from collections import Counter

ms = Counter()

ms[5] += 1
ms[3] += 1
ms[5] += 1

print(ms[5]) # 输出: 2

ms.subtract([5]) # 删除一个 5
print(ms[5]) # 输出: 1

例题2：【模板】多重集合操作

思路分析

本题要求维护一个多重集合，支持如下操作：

插入元素。
删除一个元素（如果有多个，只删除一个）。
查询某个元素的出现次数。
查询集合总元素数量（注意是元素个数，不是不同元素种类数）。
查询前驱。
查询后继。

由于普通的 set 不允许元素重复，因此需要使用 multiset<int> 来存储数据。

在 multiset 中：

insert(x) 插入一个元素（可以重复）。
erase(find(x)) 删除一个元素（注意 erase(x) 会删除所有等于 x 的元素，这里要特别注意！要先 find(x) 再删）。
count(x) 查询元素出现次数。
size() 查询总元素数量。
lower_bound(x) 和 upper_bound(x) 查找前驱和后继，与普通 set 相同。

代码实现

cpp
python

#include<bits/stdc++.h>
using namespace std;

// 全局 multiset
multiset<int> ms;

void insertValue(int x){
    ms.insert(x);
}

void eraseValue(int x){
    auto it = ms.find(x);
    if (it != ms.end()) {
        ms.erase(it); // 只删除一个
    }
}

int xCount(int x){
    return ms.count(x);
}

int sizeOfSet(){
    return ms.size();
}

int getPre(int x){
    auto it = ms.lower_bound(x);
    if (it == ms.begin()) return -1; // 没有更小的元素
    --it;
    return *it;
}

int getBack(int x){
    auto it = ms.upper_bound(x);
    if (it == ms.end()) return -1; // 没有更大的元素
    return *it;
}

int main(){
    int q, op, x;
    cin >> q;
    while (q--){
        cin >> op;
        if(op == 1){
            cin >> x;
            insertValue(x);
        }
        if(op == 2){
            cin >> x;
            eraseValue(x);
        }
        if(op == 3){
            cin >> x;
            cout << xCount(x) << endl;
        }
        if(op == 4){
            cout << sizeOfSet() << endl;
        }
        if(op == 5){
            cin >> x;
            cout << getPre(x) << endl;
        }
        if(op == 6){
            cin >> x;
            cout << getBack(x) << endl;
        }
    }
    return 0;
}

```java []

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        // 快速 IO
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        TreeMap<Integer, Integer> M = new TreeMap<>();
        long totalCount = 0;                // 维护当前多重集合中元素总数
        int n = Integer.parseInt(in.readLine().trim());

        while (n-- > 0) {
            String[] parts = in.readLine().split("\\s+");
            int opt = Integer.parseInt(parts[0]);
            int x = 0;
            if (opt != 4) {
                // 除 opt=4 外，每个操作都有第二个参数 x
                x = Integer.parseInt(parts[1]);
            }

            switch (opt) {
                case 1:
                    // 插入 x：计数 +1，总数 +1
                    M.put(x, M.getOrDefault(x, 0) + 1);
                    totalCount++;
                    break;
                case 2:
                    // 删除一个 x：存在时计数 -1，总数 -1
                    Integer cnt = M.get(x);
                    if (cnt != null) {
                        if (cnt > 1) {
                            M.put(x, cnt - 1);
                        } else {
                            M.remove(x);
                        }
                        totalCount--;
                    }
                    break;
                case 3:
                    // 查询 x 的出现次数：O(log n)
                    out.write(M.getOrDefault(x, 0).toString());
                    out.newLine();
                    break;
                case 4:
                    // 查询总大小：O(1)
                    out.write(Long.toString(totalCount));
                    out.newLine();
                    break;
                case 5:
                    // 前驱：小于 x 的最大键，O(log n)
                    Integer pre = M.lowerKey(x);
                    out.write(pre == null ? "-1" : pre.toString());
                    out.newLine();
                    break;
                case 6:
                    // 后继：大于 x 的最小键，O(log n)
                    Integer suc = M.higherKey(x);
                    out.write(suc == null ? "-1" : suc.toString());
                    out.newLine();
                    break;
            }
        }

        out.flush();
    }
}

# Python 3.8+
import sys
import bisect


def main():
    input = sys.stdin.readline
    n = int(input())
    A = []
    for _ in range(n):
        parts = input().split()
        opt = int(parts[0])
        # opt==4 时 parts 只有一个元素
        if opt != 4:
            x = int(parts[1])

        if opt == 1:
            # 插入 x
            bisect.insort(A, x)
        elif opt == 2:
            # 删除一个 x
            i = bisect.bisect_left(A, x)
            if i < len(A) and A[i] == x:
                A.pop(i)
        elif opt == 3:
            # 查询 x 个数
            l = bisect.bisect_left(A, x)
            r = bisect.bisect_right(A, x)
            print(r - l)
        elif opt == 4:
            # 查询总大小
            print(len(A))
        elif opt == 5:
            # 前驱
            i = bisect.bisect_left(A, x)
            print(A[i-1] if i > 0 else -1)
        elif opt == 6:
            # 后继
            i = bisect.bisect_right(A, x)
            print(A[i] if i < len(A) else -1)


if __name__ == "__main__":
    main()