【LeetCode】：稀疏相似度【困难】
这道题是关于计算文档相似度的问题，具体是稀疏相似度。以下是详细的解题思路：
1. 理解题目要求
- 给定一系列文档，每个文档由一个包含不同整数的数组表示（可假定每个整数代表一个单词）。
- 需要计算每对文档的相似度，相似度定义为两个文档的交集元素个数除以并集元素个数。
- 只输出相似度大于0的文档对，结果以特定格式返回，包括文档对的较小id、较大id以及相似度（精确到小数点后4位）。
2. 解题方法
- 可以使用两层循环遍历所有文档对，对于每对文档，计算它们的交集和并集元素个数，进而得到相似度。
3. 具体步骤
- 外层循环遍历文档数组
docs，从第一个文档开始，依次作为当前文档。 - 内层循环从外层循环当前文档的下一个文档开始，到文档数组的最后一个文档，依次作为与当前文档比较的文档。
- 对于每对文档：
- 创建两个集合，分别用于存储当前文档和比较文档的元素（利用集合的去重特性）。
- 计算两个集合的交集元素个数，可以使用集合的
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
最终输出结果为["0,1: 0.2500", "0,2: 0.1000"]。
这种方法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，其中 n n n是文档的数量，因为需要遍历所有文档对。空间复杂度取决于创建的集合，在最坏情况下，每个文档的元素都不同，空间复杂度为 O ( m ) O(m) O(m)，其中 m 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类型赋值给similary
double 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;
}
};