leetcode 面试17.26 稀疏相似度

一个文档可以用某个int集合来表示，两个文档的相似度定义为对应集合的交集大小除以并集大小，例如{1,5,3}与{1,7,2,3}的相似度为0.4。给定n个相似度很稀疏的文档，返回所有相似度大于0的组合。
1<=n<=500, 1<=set[i]<=500

分析：采用类似倒排索引的做法，对集合中的每个int，记录在哪些文档中出现过，然后遍历每个int，对包含该int的文档的两两组成的pair，其交集数加1。最后遍历所有pair统计结果即可。由于题目限定稀疏相似度，pair数很少，时间复度度为O(n^2)。

class Solution {
public:
    vector<string> computeSimilarities(vector<vector<int>>& docs) {
        int n = docs.size();
        std::map<int,std::vector<int>> mp;
        for (int i = 0; i < n; i++) {
            for (auto u : docs[i]) {
                mp[u].push_back(i);
            }
        }
        std::map<std::pair<int,int>,int> cnt;
        for (auto &[k,v] : mp) {
            int m = v.size();
            for (int i = 0; i < m; i++) {
                for (int j = i + 1; j < m; j++) {
                    std::pair<int,int> pr = {v[i], v[j]};
                    cnt[pr] += 1;
                }
            }
        }
        char buf[32];
        std::vector<std::string> ans;
        for (auto &[pr,v] : cnt) {
            int A = v;
            int B = docs[pr.first].size() + docs[pr.second].size() - A;
            sprintf(buf, "%d,%d: %.4f", pr.first, pr.second, 1E-8 + 1.0 * A / B);
            ans.push_back(buf);
        }
        return ans;
    }
};

注意，这里可能会有精度问题，例如，1/32的准确值为0.03125，由于计算机表示精度的原因，实际保存的值可能是0.0312499999或者0.03125000001等，如果是前者，结果就是0.0312，导致错误，因此要加eps。