交集并集题目(交集并集题目解析,简单)
作者：投稿发布时间：2022年12月04日 09:40分类：最新浏览：19
题目难度: 困难
原题链接
题目描述今天继续更新程序员面试金典系列, 大家在
算法精选
里回复面试金典
就能看到该系列当前连载的所有文章了, 记得关注哦~
两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。
输入为一个二维数组 docs，docs 表示 id 为 i 的文档。返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，其格式为 {id1},{id2}: {similarity}，其中 id1 为两个文档中较小的 id，similarity 为相似度，精确到小数点后 4 位。以任意顺序返回数组均可。
示例:- 输入:
,
,
,
]
- 输出:
提示：
- docs.length <= 500
- docs.length <= 500
- 如何优化时间复杂度?
- 分析题目, 一个很容易想到的思路就是两重循环遍历所有文档对, 然后利用集合交集和并集求相似度
- 但这样就无法利用题目所说的“相似度非常稀疏”这一条件了, 即使只有一对文档有交集, 仍需要遍历所有文档, 效率较差
- 那该如何优化呢?
- 如果我们能够知道哪些文档包含共同的单词, 这样就可以只针对这些文档来求相似度了
- 这就是典型的
倒排索引
的思路, 我们维护一个单词到包含它的所有文档 id 的映射字典 - 然后遍历每个文档的所有单词, 将映射关系更新到该字典中, 这就构建出了倒排索引
- 最后基于每个单词, 再进行两重循环来求所有包含该单词的文档对的相似对
- 因为这些文档对至少都包含当前这个单词, 所以相似度肯定不为 0
- 这样就能充分利用到稀疏这一条件了, 避免大量的相似度为 0 的无意义计算
- 另外这里需要额外引入一个文档对到相似度的映射字典, 从而避免重复计算
- 还有就是需要引入一个很小的小数, 来修正浮点数计算的精度误差
- 下面代码有非常详细的注释, 方便大家理解
- 时间复杂度 O(N^3): 最差情况(任意一对文档都有交集)时需要遍历所有文档对(O(N^2)), 然后求其相似度(O(N)), 但输入数据很稀疏, 采用倒排索引优化后无需遍历所有文档对, 所以实际的时间复杂度会远小于它
- 空间复杂度 O(N): 需要额外存储倒排索引和相似度字典
class Solution:
def computeSimilarities(self, docs: List]) -> List:
# 倒排索引字典: {word:ids}
w2i = collections.defaultdict(list)
for i, doc in enumerate(docs):
for word in doc:
# 求每个单词被包含的所有文档id列表, 即倒排索引
w2i.append(i)
docs =
# 文档对到相似度的映射字典: {(id1,id2):sim}
d2s = {}
# 需额外加上一个小数, 从而修正精度误差
EPS = 1e-9
for ids in w2i.values():
for i in range(len(ids)):
for j in range(i + 1, len(ids)):
# 当前文档id列表中的任意两文档之间都有交集, 计算其相似度
id1, id2 = ids, ids
if (id1, id2) not in d2s:
# 注意只有当该文档对不存在于相似度字典时才求相似度, 避免重复计算
d2s = len(docs & docs) / len(docs | docs) + EPS
res =
for (id1, id2), sim in d2s.items():
# 转成题目要求的输出格式, 注意加上一个小数来修正精度误差
res.append(f"{id1},{id2}: {sim+EPS:.4f}")
return res
参考资料
原题链接: https://leetcode.cn/problems/sparse-similarity-lcci/