给定集合组如何高效查找存在至少一个公共元素的集合

问题描述 #

假设我们给定一个由多个集合组成的集合组，示例如下：

Set<String> s1 = Set.of("1", "2", "3", "4", "5", "7");
Set<String> s2 = Set.of("10", "20", "30", "40", "50");
Set<String> s3 = Set.of("100", "200", "300", "400", "500", "7", "9");
Set<String> s4 = Set.of("1000", "2000", "3000", "4000", "5000");
Set<String> s5 = Set.of("100000", "200000", "300000", "400000", "500000", "9");

需求是找出所有存在元素交集的集合组合，本示例中符合要求的组合为s1&s3、s3&s5。
原有低效实现的时间复杂度较高，代码如下：

List<Set<String>> sets = List.of(s1, s2, s3, s4, s5);
for (Set<String> tester : sets) {
    sets.remove(tester);
    for (String s: tester) {
        for (Set<String> target : sets) {
            if (target.contains(s)) {
                // record match
            }
        }
    }
}

优化方案 #

核心思路 #

通过反向索引大幅降低时间复杂度：

1. 建立元素到包含该元素的集合列表的映射表
2. 遍历所有集合的所有元素，填充上述映射表
3. 遍历映射表中的所有值，若某个元素对应的集合列表长度≥2，则该列表中的所有两两集合对都是存在交集的组合
4. 对最终得到的组合去重，避免重复记录同一对集合

该方案的时间复杂度为O(m + C)，其中m为所有集合的总元素数，C为交集配对的总数量，远低于原有方案的O(n²m)（n为集合总数），在集合数量多、元素重复率低的场景下优势尤其明显。

代码实现 #

import java.util.*;
import java.util.AbstractMap.SimpleEntry;

public class SetIntersectionFinder {
    public static void main(String[] args) {
        // 给集合绑定名称方便输出
        Map<String, Set<String>> nameToSet = Map.of(
                "s1", Set.of("1", "2", "3", "4", "5", "7"),
                "s2", Set.of("10", "20", "30", "40", "50"),
                "s3", Set.of("100", "200", "300", "400", "500", "7", "9"),
                "s4", Set.of("1000", "2000", "3000", "4000", "5000"),
                "s5", Set.of("100000", "200000", "300000", "400000", "500000", "9")
        );

        // 1. 构建反向索引
        Map<String, List<String>> elementToSetNames = new HashMap<>();
        for (Map.Entry<String, Set<String>> entry : nameToSet.entrySet()) {
            String setName = entry.getKey();
            Set<String> elements = entry.getValue();
            for (String ele : elements) {
                elementToSetNames.computeIfAbsent(ele, k -> new ArrayList<>()).add(setName);
            }
        }

        // 2. 收集去重后的交集组合
        Set<SimpleEntry<String, String>> result = new HashSet<>();
        for (List<String> setNames : elementToSetNames.values()) {
            int size = setNames.size();
            if (size < 2) continue;
            // 生成两两组合，统一顺序避免重复记录同一对
            for (int i = 0; i < size; i++) {
                for (int j = i + 1; j < size; j++) {
                    String a = setNames.get(i);
                    String b = setNames.get(j);
                    if (a.compareTo(b) > 0) {
                        String temp = a;
                        a = b;
                        b = temp;
                    }
                    result.add(new SimpleEntry<>(a, b));
                }
            }
        }

        // 输出结果
        for (SimpleEntry<String, String> pair : result) {
            System.out.println(pair.getKey() + " 和 " + pair.getValue() + " 存在交集");
        }
    }
}

运行结果 #

s1 和 s3 存在交集
s3 和 s5 存在交集

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