LeetCode 面试题 17.26. 稀疏相似度
目录
题目描述
题意分析
每篇文档由一组互不重复的整数单词 ID 表示。两篇文档的相似度是 Jaccard 值
|A∩B| / |A∪B|，只输出相似度大于 0 的文档对，格式保留四位小数并按文档编号有序。文档“稀疏”的含义是绝大多数文档对没有共同单词。两两枚举所有文档再求交集会把时间浪费在大量零相似度对上。
倒排索引把方向反过来：对每个单词记录出现在哪些文档。只有同一个列表中的文档对才有非空交集，因此只为这些对累计共享单词数。
解法：倒排索引累计交集
核心思路
先构建
word -> docIds。对每个单词的文档列表，枚举其中所有i<j的组合，把 pair 的交集计数加一。题目保证单篇文档内单词不重复，所以一个单词对同一文档对只贡献一次。用
pairKey = i×N+j编码i<j。因为0<=j<N，这个编码无冲突；排序 pairKey 等价于先按 i、再按 j 排序。已知交集 intersection 后，并集为
len(doc[i])+len(doc[j])-intersection，最后做浮点除法与四位格式化。例：
docs=[[1,2,3],[2,3,4],[5]]。单词 2、3 都让 pair (0,1) 加一，交集为 2，并集为3+3-2=4，输出"0,1: 0.5000"；文档 2 与任何文档都无交集，不输出。
解题步骤
- 扫描所有文档，向每个 word 的倒排列表加入 docId。
- 对每条倒排列表排序，并枚举所有文档对，累计交集次数。
- 收集出现过的 pairKey 并升序排序。
- 解码出两个文档编号，计算并集和浮点相似度。
- 按
i,j: 0.xxxx格式加入答案。
代码实现
class Solution {
public List<String> computeSimilarities(int[][] docs) {
int docCount = docs.length;
Map<Integer, List<Integer>> wordToDocs = new HashMap<>();
for (int docId = 0; docId < docCount; docId++) {
for (int word : docs[docId]) {
wordToDocs.computeIfAbsent(word, key -> new ArrayList<>()).add(docId);
}
}
Map<Long, Integer> pairToIntersection = new HashMap<>();
for (List<Integer> docIds : wordToDocs.values()) {
Collections.sort(docIds);
for (int left = 0; left < docIds.size(); left++) {
for (int right = left + 1; right < docIds.size(); right++) {
int firstDoc = docIds.get(left);
int secondDoc = docIds.get(right);
long pairKey = (long) firstDoc * docCount + secondDoc;
pairToIntersection.put(pairKey, pairToIntersection.getOrDefault(pairKey, 0) + 1);
}
}
}
List<Long> pairKeys = new ArrayList<>(pairToIntersection.keySet());
Collections.sort(pairKeys);
List<String> answer = new ArrayList<>();
for (long pairKey : pairKeys) {
int firstDoc = (int) (pairKey / docCount);
int secondDoc = (int) (pairKey % docCount);
int intersection = pairToIntersection.get(pairKey);
int union = docs[firstDoc].length + docs[secondDoc].length - intersection;
double similarity = (double) intersection / union;
answer.add(String.format("%d,%d: %.4f", firstDoc, secondDoc, similarity + 1e-9));
}
return answer;
}
}
func computeSimilarities(docs [][]int) []string {
docCount := len(docs)
wordToDocs := map[int][]int{}
for docId, doc := range docs {
for _, word := range doc {
wordToDocs[word] = append(wordToDocs[word], docId)
}
}
pairToIntersection := map[int]int{}
for _, docIds := range wordToDocs {
sort.Ints(docIds)
for left := 0; left < len(docIds); left++ {
for right := left + 1; right < len(docIds); right++ {
firstDoc := docIds[left]
secondDoc := docIds[right]
pairKey := firstDoc * docCount + secondDoc
pairToIntersection[pairKey]++
}
}
}
pairKeys := make([]int, 0, len(pairToIntersection))
for pairKey := range pairToIntersection {
pairKeys = append(pairKeys, pairKey)
}
sort.Ints(pairKeys)
answer := make([]string, 0, len(pairKeys))
for _, pairKey := range pairKeys {
firstDoc := pairKey / docCount
secondDoc := pairKey % docCount
intersection := pairToIntersection[pairKey]
union := len(docs[firstDoc]) + len(docs[secondDoc]) - intersection
similarity := float64(intersection) / float64(union)
answer = append(answer, fmt.Sprintf("%d,%d: %.4f", firstDoc, secondDoc, similarity+1e-9))
}
return answer
}
复杂度分析
- 设 T 为所有文档的单词出现总数，
f_w为单词 w 出现的文档数，P 为相似度非零的文档对数。- 时间复杂度：
O(T + Σ_w f_w^2 + P log P)。第一项建索引，第二项枚举共享该词的文档对，第三项排序输出对。- 空间复杂度：
O(T + P)，倒排列表保存 T 个 docId，交集表最多保存 P 个 pair。
关键点总结
- 稀疏问题优先从“只生成可能非零的候选”入手，倒排索引正是候选生成器。
- 交集计数后用容斥公式得到并集，不需要重新构建集合。
- pairKey 的进制必须是文档总数 N，且固定 i<j，才能唯一编码并保持排序。
- 面试追问若某些高频词出现在几乎所有文档中，
f_w^2会成为瓶颈；可过滤停用词、用位图批量求交，或在允许近似时使用 MinHash/LSH。
易错点总结
- 两两输出所有文档对：会产生大量
0.0000，题目要求只输出非零相似度。- 错误写法：把并集写成两个文档长度直接相加。以题目示例为反例，这会把并集算成 6，得到 0.3333；正确并集要减一次交集，结果是 0.5000。
- 整数除法后再转浮点：
2/4先得到 0，再格式化为 0.0000；必须在除法前转 double/float64。- pairKey 用
i+j或固定常数进制：不同文档对会碰撞并混在一起，应使用i×N+j。- 直接遍历哈希表输出：顺序不稳定，必须排序 pairKey。
- 若输入允许文档内重复词却不去重：同一单词会把交集重复累计；本题依赖“单篇内单词互异”的约束，泛化时需先去重。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 349. 两个数组的交集 | 简单 | 两个集合的去重交集 |
| 350. 两个数组的交集 II | 简单 | 带频次的交集 |
| 737. 句子相似性 II | 中等 | 相似关系建模与并查集 |