题目难度: 困难

****

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。

输入为一个二维数组 docs，docs[i]  表示  id 为 i 的文档。返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，其格式为 {id1},{id2}: {similarity}，其中 id1 为两个文档中较小的 id，similarity 为相似度，精确到小数点后 4 位。以任意顺序返回数组均可。

示例:

  • 输入:
[
  [14, 15, 100, 9, 3],
  [32, 1, 9, 3, 5],
  [15, 29, 2, 6, 8, 7],
  [7, 10]
]
  • 输出:
[
  "0,1: 0.2500",
  "0,2: 0.1000",
  "2,3: 0.1429"
]

提示：

  • docs.length <= 500
  • docs[i].length <= 500

题目思考

  1. 如何优化时间复杂度?

解决方案

思路

  • 分析题目, 一个很容易想到的思路就是两重循环遍历所有文档对, 然后利用集合交集和并集求相似度
  • 但这样就无法利用题目所说的“相似度非常稀疏”这一条件了, 即使只有一对文档有交集, 仍需要遍历所有文档, 效率较差
  • 那该如何优化呢?
  • 如果我们能够知道哪些文档包含共同的单词, 这样就可以只针对这些文档来求相似度了
  • 这就是典型的倒排索引的思路, 我们维护一个单词到包含它的所有文档 id 的映射字典
  • 然后遍历每个文档的所有单词, 将映射关系更新到该字典中, 这就构建出了倒排索引
  • 最后基于每个单词, 再进行两重循环来求所有包含该单词的文档对的相似对
  • 因为这些文档对至少都包含当前这个单词, 所以相似度肯定不为 0
  • 这样就能充分利用到稀疏这一条件了, 避免大量的相似度为 0 的无意义计算
  • 另外这里需要额外引入一个文档对到相似度的映射字典, 从而避免重复计算
  • 还有就是需要引入一个很小的小数, 来修正浮点数计算的精度误差
  • 下面代码有非常详细的注释, 方便大家理解

复杂度

  • 时间复杂度 O(N^3): 最差情况(任意一对文档都有交集)时需要遍历所有文档对(O(N^2)), 然后求其相似度(O(N)), 但输入数据很稀疏, 采用倒排索引优化后无需遍历所有文档对, 所以实际的时间复杂度会远小于它
  • 空间复杂度 O(N): 需要额外存储倒排索引和相似度字典

代码

class Solution:
    def computeSimilarities(self, docs: List[List[int]]) -> List[str]:
        # 倒排索引字典: {word:ids}
        w2i = collections.defaultdict(list)
        for i, doc in enumerate(docs):
            for word in doc:
                # 求每个单词被包含的所有文档id列表, 即倒排索引
                w2i[word].append(i)
        docs = [set(d) for d in 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[i], ids[j]
                    if (id1, id2) not in d2s:
                        # 注意只有当该文档对不存在于相似度字典时才求相似度, 避免重复计算
                        d2s[id1, id2] = len(docs[id1] & docs[id2]) / len(docs[id1] | docs[id2]) + EPS
        res = []
        for (id1, id2), sim in d2s.items():
            # 转成题目要求的输出格式, 注意加上一个小数来修正精度误差
            res.append(f"{id1},{id2}: {sim+EPS:.4f}")
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

***********

*******

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我