【LeetCode】：稀疏相似度【困难】

这道题是关于计算文档相似度的问题，具体是稀疏相似度。以下是详细的解题思路：

1. 理解题目要求

• 给定一系列文档，每个文档由一个包含不同整数的数组表示（可假定每个整数代表一个单词）。
• 需要计算每对文档的相似度，相似度定义为两个文档的交集元素个数除以并集元素个数。
• 只输出相似度大于0的文档对，结果以特定格式返回，包括文档对的较小id、较大id以及相似度（精确到小数点后4位）。

2. 解题方法

• 可以使用两层循环遍历所有文档对，对于每对文档，计算它们的交集和并集元素个数，进而得到相似度。

3. 具体步骤

1. 外层循环遍历文档数组docs，从第一个文档开始，依次作为当前文档。
2. 内层循环从外层循环当前文档的下一个文档开始，到文档数组的最后一个文档，依次作为与当前文档比较的文档。
3. 对于每对文档：
   • 创建两个集合，分别用于存储当前文档和比较文档的元素（利用集合的去重特性）。
   • 计算两个集合的交集元素个数，可以使用集合的intersection方法（如果语言支持），或者通过遍历一个集合，判断元素是否在另一个集合中来计算。
   • 计算两个集合的并集元素个数，可使用集合的union方法（如果语言支持），或者将两个集合合并后去重得到并集元素个数。
   • 根据交集和并集元素个数计算相似度，即交集元素个数除以并集元素个数。
   • 如果相似度大于0，按照要求的格式将文档对的id和相似度添加到结果数组中。

4. 示例分析

• 以输入示例[[14, 15, 100, 9, 3], [32, 1, 9, 3, 5], [15, 29, 2, 6, 8, 7], [7, 10]]为例：
  • 比较文档0[14, 15, 100, 9, 3]和文档1[32, 1, 9, 3, 5]：
    • 交集为{9, 3}，交集元素个数为2。
    • 并集为{14, 15, 100, 9, 3, 32, 1, 5}，并集元素个数为8。
    • 相似度为2 / 8 = 0.2500，满足相似度大于0，添加到结果数组。
  • 比较文档0和文档2[15, 29, 2, 6, 8, 7]：
    • 交集为{15}，交集元素个数为1。
    • 并集为{14, 15, 100, 9, 3, 29, 2, 6, 8, 7}，并集元素个数为10。
    • 相似度为1 / 10 = 0.1000，添加到结果数组。
  • 比较文档0和文档3[7, 10]：交集为空，相似度为0，不添加到结果数组。
  • 比较文档1和文档2：
    • 交集为空，相似度为0，不添加到结果数组。
  • 比较文档1和文档3：交集为空，相似度为0，不添加到结果数组。
  • 比较文档2和文档3：
    • 交集为空，相似度为0，不添加到结果数组。

最终输出结果为["0,1: 0.2500", "0,2: 0.1000"]。

这种方法的时间复杂度为$O(n^2)$，其中$n$是文档的数量，因为需要遍历所有文档对。空间复杂度取决于创建的集合，在最坏情况下，每个文档的元素都不同，空间复杂度为$O(m)$，其中$m$是所有文档中元素的总数。

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 (const auto& word : docs[i]) {mp1[word].push_back(i);}}unordered_map<int, unordered_map<int, int>> mp2;for (const auto& item : mp1) {auto& ids = item.second;for (int i = 0; i < ids.size(); ++i) {for (int j = i + 1; j < ids.size(); j++) {mp2[ids[i]][ids[j]]++;}}}// 以下是对这段代码的详细解释：// ### 整体功能// 这段代码主要用于计算文档对的相似度并将结果以特定格式存储到result向量中// ### 代码逐行解释// 1. vector<string> result;//     -//     定义了一个字符串向量result用于存储最终要返回的每对文档及其相似度的结果字符串// 2. char temp[256];//     - 定义了一个字符数组temp大小为256用于临时存储格式化后的字符串// 3. for(auto &item : mp2){//     -//     开始遍历mp2mp2是一个嵌套的unordered_map外层键是文档索引i内层键是文档索引j//     j > i值是文档i和文档j共同拥有的单词数量-//     每次循环item代表mp2中的一个元素item.first是外层键文档索引iitem.second是内层的unordered_map包含了与文档i相关的其他文档索引j以及它们共同的单词数量// 4. int id1 = item.first;//     - 将当前遍历到的外层键 文档索引i赋值给id1//     用于后续计算相似度和格式化输出// 5. for(auto &item2 : item.second){//     -//     开始遍历内层的unordered_map即与文档i相关的其他文档索引j以及共同单词数量的映射//     -//     每次循环，item2代表内层unordered_map中的一个元素item2.first是文档索引j//     item2.second是文档i和文档j共同拥有的单词数量// 6. int id2 = item2.first;//     - 将当前遍历到的内层键文档索引j 赋值给id2// 7. double similary = (double)item2.second / (docs[id1].size() +// docs[id2].size() - item2.second);- 计算文档id1和文档id2的相似度-// item2.second是两个文档共同的单词数量-// docs[id1].size()是文档id1的单词数量// docs[id2].size()是文档id2的单词数量-// 相似度的计算公式为共同单词数量除以文档id1的单词数量 +// 文档id2的单词数量 - 共同单词数量将结果转换为double类型赋值给similary// 8. sprintf(temp, "%d,%d: %0.4lf", id1, id2, similary + 1e-9); -// 使用`sprintf函数将文档索引id1// id2和相似度similary加上一个很小的值1e-9可能是为了避免精度问题格式化为字符串并存储到temp字符数组中// - 格式化后的字符串格式为"id1,id2:similary" 其中id1 和 id2 是整数// similary是保留四位小数的浮点数// 9. // cout << temp << endl; // debug//     -//     这是一行注释掉的代码，用于调试输出`temp`中的内容，在实际运行中不会执行。// 10. result.push_back(temp);-将格式化后的字符串temp添加到result向量中// 最终result向量将包含所有相似度大于0的文档对及其相似度的字符串// 这段代码通过遍历mp2 计算每对文档的相似度// 并将结果以规定的格式存储到result向量中 以便后续返回或使用这些结果vector<string> ret;char temp[256];for (const auto& item : mp2) {int id1 = item.first;for (const auto& item2 : item.second) {int id2 = item2.first;// 相似度的计算公式为 共同单词数量除以 文档id1的单词数量 +// 文档id2的单词数量 - 共同单词数量// 将结果转换为double类型赋值给similarydouble similary =(double)item2.second /(docs[id1].size() + docs[id2].size() - item2.second);sprintf(temp, "%d,%d: %0.4lf", id1, id2, similary + 1e-8);//                 我们一般认为对于浮点数的比较//                 只要两个浮点数的差值的绝对值是小于设定的误差的，那么就说这两个数是相等的// 举个例子，设定误差为1e-6// 3.0000001// 3.0000002// 差值的绝对值0.0000001是小于0.000001的所以就说这两个值是相等的ret.push_back(temp);}}return ret;}
};