1. 相似度计算问题解析
今天要讨论的是一个经典的文本相似度计算问题:给定两组单词集合,计算它们的交集大小和并集大小。这个问题在信息检索、自然语言处理等领域有广泛应用。我们先来看题目要求:
输入两组单词(A组n个,B组m个),需要输出:
- 两组中都出现的单词数量(交集大小)
- 两组所有不重复单词的总数(并集大小)
例如:
code复制输入:
3 3
Apple Banana Orange
banana orange Peach
输出:
2 // banana和orange(不区分大小写)
4 // apple, banana, orange, peach
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 核心解决思路
2.1 问题拆解
这个问题可以分解为以下几个子任务:
- 统一单词大小写(通常转为小写)
- 去除每组内部的重复单词
- 计算两组单词的交集和并集
2.2 数据结构选择
在C++中,我们有几种容器可以处理这类需求:
unordered_set:
- 自动去重
- 基于哈希表实现,查找效率O(1)
- 无序存储
unordered_map:
- 键值对存储
- 同样基于哈希表
- 可以用于统计词频等更复杂的场景
对于本题,由于我们只需要判断单词是否存在,不需要存储额外信息,unordered_set是最合适的选择。
3. 详细实现方案
3.1 基础版本实现
cpp复制#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
unordered_set<string> setA, setB, unionSet;
// 处理第一组单词
for(int i = 0; i < n; i++) {
string word;
cin >> word;
transform(word.begin(), word.end(), word.begin(), ::tolower);
setA.i
