集合

问题描述

集合是一种存储唯一元素的数据结构。
在C++中为set，Java中为HashSet，Python中为set。
它们都能自动去重，并提供高效的成员检测。

基本概念

特点

1. 元素唯一性
2. 自动去重
3. 无序性（HashSet和Python set）
4. 有序性（C++ set）
5. 高效的查找

代码实现

1. C++ Set

#include <iostream>
#include <set>
using namespace std;

int main() {
    // 创建集合
    set<int> s1;                     // 空集合
    set<int> s2 = {1, 2, 3, 2, 1};  // 使用初始化列表（自动去重）
    
    // 插入元素
    s1.insert(1);
    s1.insert(2);
    s1.insert(2);  // 重复元素不会被插入
    
    // 删除元素
    s1.erase(1);  // 删除指定元素
    
    // 查找元素
    auto it = s1.find(2);
    if (it != s1.end()) {
        cout << "Found: " << *it << endl;
    }
    
    // 集合大小
    cout << "Size: " << s1.size() << endl;
    
    // 检查元素是否存在
    if (s1.count(2) > 0) {
        cout << "2 exists in the set" << endl;
    }
    
    // 遍历集合（有序）
    for (int x : s2) {
        cout << x << " ";  // 输出：1 2 3
    }
    cout << endl;
    
    // 集合操作
    set<int> a = {1, 2, 3};
    set<int> b = {3, 4, 5};
    set<int> result;
    
    // 并集
    set_union(a.begin(), a.end(),
              b.begin(), b.end(),
              inserter(result, result.begin()));
    
    // 交集
    result.clear();
    set_intersection(a.begin(), a.end(),
                    b.begin(), b.end(),
                    inserter(result, result.begin()));
    
    return 0;
}

2. Java HashSet

import java.util.HashSet;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        // 创建集合
        HashSet<Integer> s1 = new HashSet<>();           // 空集合
        HashSet<Integer> s2 = new HashSet<>(Arrays.asList(1, 2, 3, 2, 1));  // 使用列表初始化
        
        // 添加元素
        s1.add(1);
        s1.add(2);
        s1.add(2);  // 重复元素不会被添加
        
        // 删除元素
        s1.remove(1);  // 删除指定元素
        
        // 集合大小
        System.out.println("Size: " + s1.size());
        
        // 检查元素是否存在
        if (s1.contains(2)) {
            System.out.println("2 exists in the set");
        }
        
        // 遍历集合（无序）
        for (int x : s2) {
            System.out.print(x + " ");
        }
        System.out.println();
        
        // 集合操作
        HashSet<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3));
        HashSet<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5));
        
        // 并集
        HashSet<Integer> union = new HashSet<>(a);
        union.addAll(b);
        
        // 交集
        HashSet<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);
        
        // 差集
        HashSet<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);
    }
}

3. Python Set

# 创建集合
s1 = set()                    # 空集合
s2 = {1, 2, 3, 2, 1}         # 使用字面量（自动去重）
s3 = set([1, 2, 3, 2, 1])    # 从列表创建

# 添加和删除
s1.add(1)           # 添加元素
s1.add(2)
s1.add(2)          # 重复元素不会被添加
s1.remove(1)        # 删除元素（元素不存在会报错）
s1.discard(3)       # 删除元素（元素不存在不会报错）

# 集合大小
print(len(s1))      # 获取大小

# 成员检测
if 2 in s1:
    print("2 exists in the set")

# 遍历集合（无序）
for x in s2:
    print(x, end=" ")
print()

# 集合操作
a = {1, 2, 3}
b = {3, 4, 5}

# 并集
union = a | b       # 或者 a.union(b)
print(union)        # {1, 2, 3, 4, 5}

# 交集
inter = a & b       # 或者 a.intersection(b)
print(inter)        # {3}

# 差集
diff = a - b        # 或者 a.difference(b)
print(diff)         # {1, 2}

# 对称差集
sym_diff = a ^ b    # 或者 a.symmetric_difference(b)
print(sym_diff)     # {1, 2, 4, 5}

# 子集和超集
subset = {1, 2}
print(subset <= a)  # True: subset是a的子集
print(a >= subset)  # True: a是subset的超集

应用场景

1. 去重处理
2. 成员检测
3. 集合运算
4. 数据过滤
5. 唯一性约束

注意事项

1. 元素类型要求
2. 无序性（HashSet和Python set）
3. 有序性（C++ set）
4. 性能特征
5. 元素可哈希性

常见示例

1. 数组去重

vector<int> unique(vector<int>& nums) {
    set<int> s(nums.begin(), nums.end());
    return vector<int>(s.begin(), s.end());
}

public static List<Integer> unique(List<Integer> nums) {
    return new ArrayList<>(new HashSet<>(nums));
}

def unique(nums: list) -> list:
    return list(set(nums))

2. 交集计算

vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    set<int> s1(nums1.begin(), nums1.end());
    set<int> s2(nums2.begin(), nums2.end());
    vector<int> result;
    set_intersection(s1.begin(), s1.end(),
                    s2.begin(), s2.end(),
                    back_inserter(result));
    return result;
}

public static Set<Integer> intersection(List<Integer> nums1, List<Integer> nums2) {
    HashSet<Integer> set1 = new HashSet<>(nums1);
    HashSet<Integer> set2 = new HashSet<>(nums2);
    set1.retainAll(set2);
    return set1;
}

def intersection(nums1: list, nums2: list) -> list:
    return list(set(nums1) & set(nums2))