交集并集题目(交集并集题目解析,简单)-欢鸽网
右侧
欢鸽网
当前位置:网站首页 > 最新 > 正文

交集并集题目(交集并集题目解析,简单)

作者:投稿发布时间: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
题目思考
  1. 如何优化时间复杂度?
解决方案思路
  • 分析题目, 一个很容易想到的思路就是两重循环遍历所有文档对, 然后利用集合交集和并集求相似度
  • 但这样就无法利用题目所说的“相似度非常稀疏”这一条件了, 即使只有一对文档有交集, 仍需要遍历所有文档, 效率较差
  • 那该如何优化呢?
  • 如果我们能够知道哪些文档包含共同的单词, 这样就可以只针对这些文档来求相似度了
  • 这就是典型的

    倒排索引

    的思路, 我们维护一个单词到包含它的所有文档 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/


欢鸽网| 沪ICP备2021003167号 网站地图