LeetCode 面试题 17.26. 稀疏相似度
题目描述
题意分析
每篇文档由一组互不重复的整数单词表示，文档编号就是数组下标。两文档的相似度为交集大小除以并集大小，只输出相似度大于零的文档对，较小编号在前，数值格式化为四位小数；结果数组的组间顺序任意，空文档忽略。
解法：倒排索引只累计非零交集
核心思路
[!blue]
只有共享至少一个单词的文档对才需要输出。逐对比较所有文档会把大量时间花在交集为空的组合上，可以反过来从单词出发：用
wordToDocs[word]保存包含这个词的所有文档编号，也就是倒排索引。对某个单词，枚举它的列表中全部不同文档对，为每对的交集计数加一。单篇文档内没有重复词，所以一个文档在该列表中只出现一次，这个词也只给同一文档对贡献一次。处理全部单词后，一对文档被累加的次数，恰好等于它们共享的不同单词数。
这种方式不会漏掉需要输出的组合：交集非空的任意文档对，总能在至少一个共同词的列表中被枚举到；交集为空的组合不会出现在任何同词列表中，也就不会被写入计数表。空文档没有词，自然不会进入任何列表，无需额外计算零相似度。
建表时按文档编号升序扫描，倒排列表也天然升序。在同一个列表里只取
left < right的两个位置，就能保证firstDoc < secondDoc，每对只按一个方向记录。代码用firstDoc * N + secondDoc编码文档对，其中N是文档总数；因为第二个编号在[0, N)内，整除与取余可以唯一还原两个编号，不会混淆不同组合。对每个已记录的正交集，使用集合恒等式
union = len(first) + len(second) - intersection得到并集，再做浮点除法。两篇长度相加时，共同元素被算了两次，所以必须减去一份交集。最后按指定格式输出四位小数；原实现加上很小的1e-9修正，处理本题有限文档长度下的舍入临界值，而不是截断小数。
解题步骤
- 按文档编号遍历每个词，建立单词到文档编号列表的映射。
- 对每个列表枚举两两不同编号，编码成键并增加对应交集计数。
- 遍历交集计数表，解码文档编号，用两文档长度求并集。
- 计算浮点相似度，格式化为
id1,id2: similarity，保留四位小数后返回。
代码实现
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()) {
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<String> answer = new ArrayList<>();
for (long pairKey : pairToIntersection.keySet()) {
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;
}
}
import (
"fmt"
)
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 {
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]++
}
}
}
answer := make([]string, 0, len(pairToIntersection))
for pairKey, intersection := range pairToIntersection {
firstDoc := pairKey / docCount
secondDoc := pairKey % docCount
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
}
复杂度分析
- 时间复杂度：期望 $O(N+T+\sum_w f_w^2)$，其中
N是文档数、T是全部词条数，f_w是包含词w的文档数量。建表处理全部词条，每个倒排列表枚举 $\binom{f_w}{2}$ 对；非零组合的输出数量也被这些枚举次数覆盖。- 空间复杂度：$O(T+P+1)$，其中
P是交集非空的文档对数，用于倒排列表、交集计数与结果。
关键点总结
[!green]
- 按共同词枚举文档对，直接跳过所有没有共享词的组合。
- 文档内部词互异，保证每个共同词恰好为交集贡献一次。
- 倒排列表已经按编号有序，输出数组也不要求排序，二者都无需额外排序。
易错点总结
[!yellow]
- 不能把单词出现的文档数直接当作交集，交集要按每个具体文档对分别累计。
- 并集必须从两文档长度之和中减去交集，且除法前要转成浮点类型。
- 配对时只枚举列表中不同的两个位置，避免自身配对与正反重复。
- 编码和解码都必须使用同一个文档总数
N，不能改用某个倒排列表的长度。- 删除高频词会改变原文档的交并集，不能作为精确相似度算法的剪枝。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 350. 两个数组的交集 II | 简单 | 同样求交集，本题输入是集合并要求多组非零交集，倒排索引避免枚举无共同词的文档对。 |
| 补充题 168. 汉字总频次与文档频次统计 | 中等 | 同样区分词频与出现文档集合，本题进一步用共享文档列表累计文档对交集。 |