海城建设网站,泰安有哪些景点,东莞公司品牌网站建设,百度网址链接收录提交入口1. 题目
两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数#xff0c;就是这两个文档的相似度。
例如#xff0c;{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4#xff0c;其中#xff0c;交集的元素有 2 个#xff0c;并集的元素有 …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 为两个文档中较小的 idsimilarity 为相似度精确到小数点后 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
相似度大于 0 的文档对数不会超过 1000来源力扣LeetCode 链接https://leetcode-cn.com/problems/sparse-similarity-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
题目说稀疏最多1000对考虑相同的 文档内容后面存储《含有该内容的文档 id》sprintf(res, %d,%d: %.4f, id1, id2, similarity1e-9);精度问题参考评论区1e-9C 库函数 int sprintf(char *str, const char *format, ...) 发送格式化输出到 str 所指向的字符串卡精度例子拿走不客气
class Solution {
public:vectorstring computeSimilarities(vectorvectorint docs) {unordered_mapint,vectorint m;//文档片段含有该片段的文档idfor(int i 0; i docs.size(); i){for(int part : docs[i])m[part].push_back(i);}unordered_mapint,unordered_mapint,int countSame;//doc1doc2sameValueint i, j, id1, id2, num;for(auto mi : m){for(i 0; i mi.second.size()-1; i){id1 mi.second[i];for(j i1; j mi.second.size(); j){id2 mi.second[j];countSame[id1][id2] 1;}}}vectorstring ans;double similarity;for(auto vals : countSame){id1 vals.first;for(auto count : vals.second){id2 count.first;num count.second;similarity double(num)/(docs[id1].size()docs[id2].size()-num);char res[16];sprintf(res, %d,%d: %.4f, id1, id2, similarity1e-9);ans.push_back(string(res,res16));}}return ans;}
};
