1. Jaccard相似度基础概念第一次接触Jaccard相似度是在准备CCF-CSP考试时当时看到这个数学公式有点懵。后来发现它其实特别生活化——就像比较两个朋友的口味相似度。比如你和朋友A都爱吃火锅、烧烤、日料这就是交集而把你们爱吃的所有食物放在一起统计就是并集。Jaccard相似度的计算公式很简单 [ Sim(A,B) \frac{|A \cap B|}{|A \cup B|} ]这个公式的核心思想是共同拥有的元素占比越大相似度越高。在实际应用中它特别适合处理非数值型数据的相似度比较比如文章关键词相似度本题场景用户购物偏好分析社交网络好友关系分析考试题目中特别强调要忽略大小写差异这个细节很关键。就像在实际开发中New York和new york应该被视为同一个地点。我刚开始做这道题时就是因为漏了大小写转换导致测试用例一直过不去。2. 题目分析与解题思路拆解拿到这道题时我习惯先画个流程图。整个计算过程可以分为四个关键步骤数据预处理将所有单词统一转为小写集合构建去除重复单词构建两个集合集合运算计算交集和并集的大小结果输出按要求格式输出这里有个容易踩的坑直接使用数组存储会浪费大量时间在查找操作上。比如用线性查找判断元素是否存在时间复杂度会变成O(n²)当n10⁴时就可能超时。我第一版代码就是这样写的结果在最大规模测试用例上跑了1.5秒限时1秒。更聪明的做法是用哈希集合HashSet它的查找时间复杂度是O(1)。在C中可以用unordered_setPython直接用set()就行。这也是为什么题目特别强调去掉重复单词——暗示我们要用集合的特性。3. C高效实现方案先看我最推荐的STL算法方案。这个版本代码简洁运行效率高实测15ms左右#include iostream #include set #include algorithm using namespace std; string toLower(string s) { for(char c : s) c tolower(c); return s; } int main() { int n, m; cin n m; setstring setA, setB; string word; // 构建集合A while(n--) { cin word; setA.insert(toLower(word)); } // 构建集合B while(m--) { cin word; setB.insert(toLower(word)); } // 计算交集和并集 setstring intersection, unionSet; set_intersection(setA.begin(), setA.end(), setB.begin(), setB.end(), inserter(intersection, intersection.begin())); set_union(setA.begin(), setA.end(), setB.begin(), setB.end(), inserter(unionSet, unionSet.begin())); cout intersection.size() endl; cout unionSet.size() endl; return 0; }这个实现有几个优化点使用set自动去重不需要手动判断元素是否已存在STL算法直接计算set_intersection和set_union封装了高效的集合运算时间复杂度分析构建集合O(nlogn mlogm)集合运算O(nm)不过要注意set在C中是基于红黑树实现的如果追求极致速度可以用unordered_set哈希实现。但实测在本题数据规模下差异不大。4. Python简洁实现方案对于Python选手这道题简直是送分题——利用Python强大的集合操作代码可以非常简洁n, m map(int, input().split()) setA {word.lower() for word in input().split()} setB {word.lower() for word in input().split()} print(len(setA setB)) print(len(setA | setB))是的就这6行代码Python的集合运算符号非常直观表示交集|表示并集-表示差集不过要注意两个性能陷阱不要用list代替setlist的in操作是O(n)复杂度避免多次转换大小写在构建集合时一次性转换好我在实际测试中发现Python版本的运行时间大约是C的3-5倍但在CCF-CSP的评测环境下依然能轻松通过所有测试点。5. 常见错误与调试技巧在帮学弟学妹debug这道题时我发现了一些高频错误点案例1大小写处理遗漏// 错误示例忘记转换大小写 setA.insert(word); // 错误应该先转小写案例2错误计算并集大小// 错误示例直接相加两个集合大小 int unionSize setA.size() setB.size(); // 这样会重复计算交集部分案例3使用vector导致超时vectorstring wordsA; // 每次插入前线性查找是否已存在 if(find(wordsA.begin(), wordsA.end(), word) wordsA.end()) wordsA.push_back(word); // 当n1e4时这种写法必然超时调试时可以构造这些边界测试用例全大写 vs 全小写测试大小写转换输入2 2 HELLO WORLD hello world 输出2 2完全相同的文章测试去重逻辑输入3 3 a a a a a a 输出1 1超大输入测试准备1万个单词的文本检查程序是否能在1秒内完成6. 性能优化与进阶思考虽然上面的解法已经能拿满分但如果我们想进一步优化可以考虑优化1使用更快的IO方式ios::sync_with_stdio(false); cin.tie(0); // 取消cin与cout的同步加速IO优化2手动实现哈希集合对于特别大的数据集可以自定义哈希函数来减少冲突。进阶思考如果题目要求输出具体的交集和并集元素该如何修改代码这时候就需要保留完整的集合内容而不仅仅是计算大小。可以这样调整// 输出交集元素 for(const auto word : intersection) cout word ; cout endl; // 输出并集元素 for(const auto word : unionSet) cout word ;实际工程中Jaccard相似度常用于推荐系统。比如根据用户浏览记录计算商品相似度def item_similarity(item1_views, item2_views): set1 set(item1_views) # 浏览过商品1的用户集合 set2 set(item2_views) # 浏览过商品2的用户集合 return len(set1 set2) / len(set1 | set2)7. 其他语言实现对比为了帮助使用不同语言的同学这里给出Java的实现方案import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); SetString setA new HashSet(); SetString setB new HashSet(); // 读取集合A for(int i0; in; i) { setA.add(sc.next().toLowerCase()); } // 读取集合B for(int i0; im; i) { setB.add(sc.next().toLowerCase()); } // 计算交集 SetString intersection new HashSet(setA); intersection.retainAll(setB); // 计算并集 SetString union new HashSet(setA); union.addAll(setB); System.out.println(intersection.size()); System.out.println(union.size()); } }Java的集合API也很强大注意两点retainAll()相当于求交集addAll()相当于求并集不同语言的集合操作对比操作CPythonJava创建集合setset()HashSet()添加元素insert()add()add()求交集set_intersection()retainAll()求并集set_union()8. 实际应用与扩展学习Jaccard相似度在真实场景中的应用远比考试题目丰富。我在工作中就用它解决过这些问题文档去重计算两篇文章的词汇相似度过滤重复内容用户画像匹配通过比较用户兴趣标签寻找相似用户推荐系统基于用户历史行为推荐相似商品如果想深入学习可以探索这些进阶方向加权Jaccard考虑元素的权重如词频MinHash算法用于大规模数据集相似度估算局部敏感哈希(LSH)高效近邻搜索技术一个实用的工具推荐Python的datasketch库提供了MinHash实现适合处理海量数据from datasketch import MinHash m1 MinHash() m2 MinHash() # 分别添加元素到m1和m2 similarity m1.jaccard(m2) # 估算Jaccard相似度最后给备考的同学一个建议CCF-CSP的第二题通常考察基础数据结构的应用把STL的set/map/vector这些容器玩熟就能轻松应对大部分题目。这道相似度计算题就是典型的集合操作应用题理解原理后其实相当简单。