如何检查多个给定集合中的不相交集？Java方法实现求助

首先明确需求：对于输入的每个集合，找到所有和它没有共同元素的集合，存入Map中，键是原集合，值是所有不相交集合的集合。

原代码的问题 #

你的示例代码存在几个关键问题：

1. 错误地将整个输入集合作为值存入Map，没有筛选出不相交的子集
2. 仅通过!x.equals(y)判断，这只排除了完全相同的集合，但无法识别相交但不等的集合（比如[0]和[0,4,5]）
3. 双重循环重复比较（如x和y、y和x都做了相同判断），造成不必要的性能浪费

优化实现思路 #

1. 判断不相交的高效方法：使用Collections.disjoint(Set<?> s1, Set<?> s2)，这个方法会遍历较小的集合，检查是否有元素存在于另一个集合中，一旦找到交集就立即返回false，比自己实现遍历更高效。
2. 减少重复计算：双重循环中只处理i < j的配对，一旦确定两个集合不相交，就同时将对方添加到彼此的结果集合中，这样能减少一半的循环次数。
3. 提前初始化结果容器：先为每个输入集合创建一个空的结果集合，避免后续重复创建。

修正后的代码 #

import java.util.*;

public class DisjointSetMapper {
    public <E> Map<Set<E>, Set<Set<E>>> disjointSets(Set<Set<E>> inputSets) {
        Map<Set<E>, Set<Set<E>>> result = new HashMap<>();

        // 先为每个集合初始化空的结果集合
        for (Set<E> set : inputSets) {
            result.put(set, new HashSet<>());
        }

        // 将集合转为列表，方便通过索引避免重复比较
        List<Set<E>> setList = new ArrayList<>(inputSets);
        int size = setList.size();

        // 只比较i < j的配对，减少重复计算
        for (int i = 0; i < size; i++) {
            Set<E> setA = setList.get(i);
            for (int j = i + 1; j < size; j++) {
                Set<E> setB = setList.get(j);
                // 判断两个集合是否不相交
                if (Collections.disjoint(setA, setB)) {
                    // 互相添加到对方的结果集合中
                    result.get(setA).add(setB);
                    result.get(setB).add(setA);
                }
            }
        }

        return result;
    }

    // 测试示例
    public static void main(String[] args) {
        Set<Set<Integer>> input = new HashSet<>();
        input.add(new HashSet<>(List.of(0)));
        input.add(new HashSet<>(List.of(0, 4, 5)));
        input.add(new HashSet<>(List.of(1, 2)));

        DisjointSetMapper mapper = new DisjointSetMapper();
        Map<Set<Integer>, Set<Set<Integer>>> result = mapper.disjointSets(input);

        // 打印结果验证
        for (Map.Entry<Set<Integer>, Set<Set<Integer>>> entry : result.entrySet()) {
            System.out.println(entry.getKey() + " : " + entry.getValue());
        }
    }
}

代码说明 #

• 初始化结果容器：先遍历输入集合，为每个集合创建对应的空HashSet，确保后续可以直接添加元素。
• 列表转换：将Set转为List，方便通过索引控制循环范围，避免重复比较同一对集合。
• 高效判断不相交：Collections.disjoint内部优化了遍历逻辑，优先遍历较小的集合，减少元素检查次数。
• 双向添加结果：当确定setA和setB不相交时，同时将setB加入setA的结果集合，setA加入setB的结果集合，避免重复判断。

性能说明 #

假设输入有n个集合，每个集合平均大小为k：

• 原代码时间复杂度是O(n²*k)（双重循环全量比较，每次比较可能遍历整个集合）
• 优化后的代码时间复杂度是O(n²*min(k1,k2))（仅比较一半的配对，且Collections.disjoint会选较小集合遍历），在集合数量较多时能显著减少计算量。

内容的提问来源于stack exchange，提问作者bells