題目描述

描述：兩個(gè)(具有不同單詞的)文檔的交集(intersection)中元素的個(gè)數(shù)除以并集(union)中元素的個(gè)數(shù)，就是這兩個(gè)文檔的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 個(gè)，并集的元素有 5 個(gè)。給定一系列的長(zhǎng)篇文檔，每個(gè)文檔元素各不相同，并與一個(gè) ID 相關(guān)聯(lián)。它們的相似度非?！跋∈琛?，也就是說(shuō)任選 2 個(gè)文檔，相似度都很接近 0。請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法返回每對(duì)文檔的 ID 及其相似度。只需輸出相似度大于 0 的組合。請(qǐng)忽略空文檔。為簡(jiǎn)單起見(jiàn)，可以假定每個(gè)文檔由一個(gè)含有不同整數(shù)的數(shù)組表示。

輸入為一個(gè)二維數(shù)組 docs，docs[i] 表示 id 為 i 的文檔。返回一個(gè)數(shù)組，其中每個(gè)元素是一個(gè)字符串，代表每對(duì)相似度大于 0 的文檔，其格式為 {id1},{id2}: {similarity}，其中 id1 為兩個(gè)文檔中較小的 id，similarity 為相似度，精確到小數(shù)點(diǎn)后 4 位。以任意順序返回?cái)?shù)組均可。

示例:

輸入: 
[
  [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存儲(chǔ)單詞以及單詞所出現(xiàn)的文檔集合，使用ump2存儲(chǔ)文檔以及文檔相關(guān)聯(lián)的文檔集合以及交集元素個(gè)數(shù)，再利用公式求解相似度即可。

class Solution {
public:
    vector<string> computeSimilarities(vector<vector<int>>& docs) {
        //單詞 單詞對(duì)應(yīng)的文檔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);
        }
        // 文檔 交集文檔 交集個(gè)數(shù)
        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;
    }
};

總結(jié)：ump2利用的非常巧妙，有點(diǎn)類(lèi)似于數(shù)據(jù)庫(kù)多表查詢(xún)的感覺(jué)啦！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-531332.html

到了這里，關(guān)于【程序員面試金典】面試題 17.26. 稀疏相似度的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！