package
0.0.0-20230809123828-b071cee2968a
Repository: https://github.com/codehanhan/leetcode-go.git
Documentation: pkg.go.dev

# README

面试题 17.26.稀疏相似度

1. 题目描述

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

输入为一个二维数组 docsdocs[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

标签 数组 哈希表 排序

2. 解题

本质是求n个集合两两之间的并集

求两个集合id1和id2的稀疏相似性,可以使用下面的公式 id1和id2交集个数/(id1和id2并集个数) = id1和id2交集个数/(id1和id2总个数 - id1和id2交集个数) = 稀疏相似性,所以只需要求id1和id2交集个数。

如果是求两个数组集合的交集元素,那么使用hash是比较容易想到的,也比较容易操作,只需要将一个集合hash化,然后遍历第二个集合的每个元素,从hash中判断是否存在元素。

如果是n个集合,求集合之间任意两者之间的交集元素个数。 这个时候如果使用上面的方法来求任何两个数组集合,效率就比较低。可以使用map方法,也是hash的思维。将所有集合都遍历一遍,将元素作为key,将对应的数组id作为value,一个key可以对应多个value。 接下来我们来逐一遍历key和id,使用nums[id1][id2]来记录集合id1和id2中交集个数。比如

3:1,2,5 -- 集合1,2,5中有3
遍历1,2,5。nums[1][2]++,nums[1][5]++,nums[2][5]++

6:1,5 -- 集合1,5中有6
遍历1,5。nums[1][5]++

8:1 -- 集合1中有8
只有一个元素,没法遍历

最终nums[1][3] = 1,nums[1][5] = 2,nums[2][5] = 1。