class Solution {
public:
vector<string> computeSimilarities(vector<vector<int>>& docs) {
}
};
面试题 17.26. 稀疏相似度
两个(具有不同单词的)文档的交集(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 <= 500docs[i].length <= 500原站题解
python3 解法, 执行用时: 328 ms, 内存消耗: 47.5 MB, 提交时间: 2023-04-22 12:46:55
'''
dic1[num] 记录含有num的所有doc的id
对每一个id数组，两两元素记录到dic2[i, j]，即为docs[i]与docs[j]的交集大小
'''
class Solution:
def computeSimilarities(self, docs: List[List[int]]) -> List[str]:
dic1 = collections.defaultdict(list)
for i, doc in enumerate(docs):
for num in doc:
dic1[num].append(i)
dic2 = collections.defaultdict(int)
for li in dic1.values():
for p in range(len(li)):
for q in range(p + 1, len(li)):
dic2[li[p], li[q]] += 1
res = []
minn = 1e-9
for (p, q), i in dic2.items():
u = len(docs[p]) + len(docs[q]) - i
res.append("{0:d},{1:d}: {2:.4f}".format(p, q, i / u + minn))
return res
java 解法, 执行用时: 307 ms, 内存消耗: 76.9 MB, 提交时间: 2023-04-22 12:46:20
class Solution {
public List<String> computeSimilarities(int[][] docs) {
List<String> ans = new ArrayList<>();
Map<Integer, List<Integer>> map = new HashMap<>();
int[][] help = new int[docs.length][docs.length];
for (int i = 0; i < docs.length; i++) {
for (int j = 0; j < docs[i].length; j++) {
List<Integer> list = map.get(docs[i][j]);
if (list == null) {
list = new ArrayList<>();
map.put(docs[i][j], list);
} else {
for (Integer k : list) {
help[i][k]++;
}
}
list.add(i);
}
for (int k = 0; k < docs.length; k++) {
if (help[i][k] > 0) {
ans.add(k + "," + i + ": " + String.format("%.4f", (double) help[i][k] / (docs[i].length + docs[k].length - help[i][k])));
}
}
}
return ans;
}
}
golang 解法, 执行用时: 336 ms, 内存消耗: 24.2 MB, 提交时间: 2023-04-22 12:45:46
func computeSimilarities(docs [][]int) []string {
ans := []string{}
for _, doc := range docs {
sort.Ints(doc)
}
mp := make(map[int][]int)
for i, doc := range docs {
for _, w := range doc {
if _, e := mp[w]; !e {
mp[w] = []int{}
}
mp[w] = append(mp[w], i)
}
}
d2d := make(map[int]map[int]int)
for _, darr := range mp {
sort.Ints(darr)
for i := 0; i < len(darr) - 1; i ++ {
for j := i + 1; j < len(darr); j ++ {
if _, e := d2d[darr[i]]; !e {
d2d[darr[i]] = make(map[int]int)
}
d2d[darr[i]][darr[j]] ++
}
}
}
for i := range docs {
for j := i + 1; j < len(docs); j ++ {
if _, e := d2d[i][j]; e {
res := float64(d2d[i][j]) / float64((len(docs[i]) + len(docs[j])) - d2d[i][j])
ans = append(ans, strconv.Itoa(i) + "," + strconv.Itoa(j) + ": " + fmt.Sprintf("%.4f", res + 1e-9))
}
}
}
return ans
}
cpp 解法, 执行用时: 376 ms, 内存消耗: 95.6 MB, 提交时间: 2023-04-22 12:45:25
class Solution {
public:
vector<string> computeSimilarities(vector<vector<int>>& docs) {
unordered_map<int, vector<int>> mp1;
for(int i=0; i<docs.size(); ++i){
for(auto &word : docs[i]){
mp1[word].push_back(i);
}
}
unordered_map<int, unordered_map<int, int>> mp2;
for(auto &item : mp1){
auto &ids = item.second;
for(int i=0; i+1<ids.size(); ++i){
for(int j=i+1; j<ids.size(); ++j){
mp2[ids[i]][ids[j]]++;
}
}
}
vector<string> result;
char temp[256];
for(auto &item : mp2){
int id1 = item.first;
for(auto &item2 : item.second){
int id2 = item2.first;
double similary = (double)item2.second /
(docs[id1].size() + docs[id2].size() - item2.second);
sprintf(temp, "%d,%d: %0.4lf", id1, id2, similary + 1e-9);
// cout << temp << endl; // debug
result.push_back(temp);
}
}
return result;
}
};