1. 天梯赛L2-005集合相似度题目解析这道来自天梯赛L2级别的编程题目考察的是对Java集合操作和算法设计的综合运用能力。题目要求计算两个集合的相似度这个相似度在数学上被称为Jaccard相似系数是数据挖掘和文本处理领域的常用指标。Jaccard相似系数的计算公式为 相似度 |A∩B| / |A∪B| 其中|A∩B|表示两个集合的交集元素个数|A∪B|表示并集元素个数。在实际比赛中这道题通常会给出多个测试用例每个用例包含若干集合要求计算指定集合对的相似度。输入格式一般是第一行集合个数N接下来N行每个集合的元素然后一行查询次数K最后K行每行两个集合编号要求计算它们的相似度2. Java实现方案设计2.1 数据结构选择对于这种需要频繁查询集合交并操作的问题选择合适的数据结构至关重要。在Java中我们有几种选择HashSet基于哈希表实现查找、插入、删除操作都是O(1)时间复杂度TreeSet基于红黑树实现元素有序但操作时间复杂度为O(log n)ArrayList简单列表但查找操作效率低考虑到题目主要需要高效的contains操作来计算交集和并集HashSet是最佳选择。它的contains()方法平均时间复杂度为O(1)能极大提升程序运行效率。2.2 算法流程设计完整的解决方案可以分为以下几个步骤读取所有集合数据存储为HashSet数组预处理每个集合去除重复元素HashSet自动处理对于每个查询取出对应的两个集合计算交集大小计算并集大小输出相似度保留2位小数其中计算交集和并集大小有几种实现方式我们会在下一节详细分析。3. 核心代码实现3.1 集合的存储与读取首先我们需要读取输入数据并存储集合Scanner sc new Scanner(System.in); int N sc.nextInt(); SetInteger[] sets new Set[N1]; // 使用1-based索引 for (int i 1; i N; i) { int size sc.nextInt(); sets[i] new HashSet(); for (int j 0; j size; j) { sets[i].add(sc.nextInt()); } }这里使用Set数组来存储所有集合索引从1开始以匹配题目中的集合编号。3.2 交集与并集计算计算两个集合的交集大小有几种方法方法一使用retainAll()SetInteger intersection new HashSet(set1); intersection.retainAll(set2); int intersectionSize intersection.size();方法二遍历较小集合int intersectionSize 0; for (int num : smallerSet) { if (largerSet.contains(num)) { intersectionSize; } }方法二通常效率更高特别是当一个集合远小于另一个时。我们可以进一步优化int intersectionSize 0; SetInteger smaller set1.size() set2.size() ? set1 : set2; SetInteger larger set1.size() set2.size() ? set2 : set1; for (int num : smaller) { if (larger.contains(num)) { intersectionSize; } }并集大小可以通过集合大小和交集大小计算得出int unionSize set1.size() set2.size() - intersectionSize;3.3 完整查询处理将上述部分组合起来处理查询int K sc.nextInt(); for (int i 0; i K; i) { int a sc.nextInt(); int b sc.nextInt(); SetInteger set1 sets[a]; SetInteger set2 sets[b]; int intersectionSize calculateIntersection(set1, set2); int unionSize set1.size() set2.size() - intersectionSize; double similarity (double) intersectionSize / unionSize * 100; System.out.printf(%.2f%%\n, similarity); }4. 性能优化技巧4.1 输入输出优化天梯赛中对程序运行时间有严格要求当数据量较大时标准的Scanner可能会成为性能瓶颈。可以使用BufferedReader进行优化BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int N Integer.parseInt(br.readLine()); SetInteger[] sets new Set[N1]; for (int i 1; i N; i) { st new StringTokenizer(br.readLine()); int size Integer.parseInt(st.nextToken()); sets[i] new HashSet(); for (int j 0; j size; j) { sets[i].add(Integer.parseInt(st.nextToken())); } }4.2 避免重复计算如果题目允许可以预先计算所有集合对的相似度并缓存结果。这在查询次数远大于集合数量时特别有效。4.3 内存管理对于极大的数据集可以考虑以下优化使用更紧凑的数据结构如Trove库的THashSet如果元素范围有限可以使用位图(BitSet)表示集合及时清除不再需要的中间结果5. 常见问题与调试技巧5.1 精度问题计算相似度时整数除法会导致精度丢失// 错误做法 double similarity intersectionSize / unionSize * 100; // 正确做法 double similarity (double) intersectionSize / unionSize * 100;5.2 边界条件需要特别注意的边界情况两个空集的相似度题目通常会避免这种情况完全相同的集合相似度应为100%完全没有交集的集合相似度应为0%5.3 调试建议使用小样本测试手动计算预期结果打印中间计算结果如集合大小、交集大小等检查集合编号是否从1开始很多选手在这里出错6. 扩展思考6.1 其他相似度度量除了Jaccard相似度还可以考虑余弦相似度编辑距离重叠系数6.2 大规模集合处理当集合非常大时可以考虑布隆过滤器快速判断可能存在的元素最小哈希(MinHash)估计Jaccard相似度分布式计算框架如MapReduce6.3 实际应用场景集合相似度计算在以下场景有广泛应用推荐系统用户兴趣相似度文档去重shingling算法生物信息学基因序列比对在实际编码练习中我发现对集合大小的判断和选择较小集合进行遍历能显著提高性能。另外使用BufferedReader代替Scanner在处理大规模输入时能有2-3倍的性能提升。对于天梯赛这类竞赛这些优化往往就是能否通过所有测试用例的关键。