【程序员面试金典】面试题 17.26. 稀疏相似度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 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 <= 500
docs[i].length <= 500

解题思路

思路：最直观的想法是，使用ump1存储单词以及单词所出现的文档集合，使用ump2存储文档以及文档相关联的文档集合以及交集元素个数，再利用公式求解相似度即可。

class Solution {
public:
    vector<string> computeSimilarities(vector<vector<int>>& docs) {
        //单词 单词对应的文档id
        unordered_map<int,vector<int>> ump1;
        for(int i=0;i<docs.size();i++)
        {
            for(auto word:docs[i])
                ump1[word].push_back(i);
        }
        // 文档 交集文档 交集个数
        unordered_map<int,unordered_map<int,int>> ump2;
        for(auto m:ump1)
        {
            //ids表示存在交集的文档
            auto ids=m.second;
            for(int i=0;i+1<ids.size();i++)
            {
                for(int j=i+1;j<ids.size();j++)
                {
                    ump2[ids[i]][ids[j]]++;
                }
            }
        }
        //精度误差
        vector<string> result;
        char temp[256];
        for(auto n:ump2)
        {
            int id1=n.first;
            for(auto k:n.second)
            {
                int id2=k.first;
                double similary=(double)k.second/(docs[id1].size()+docs[id2].size()-k.second);
                sprintf(temp, "%d,%d: %0.4lf", id1, id2, similary + 1e-9);
                result.push_back(temp);
            }
        }
        return result;
    }
};

总结：ump2利用的非常巧妙，有点类似于数据库多表查询的感觉啦！文章来源地址https://www.toymoban.com/news/detail-531332.html

到了这里，关于【程序员面试金典】面试题 17.26. 稀疏相似度的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！