面试题 17.26. 稀疏相似度¶
Tags: Hard Hash Table
Links: https://leetcode-cn.com/problems/sparse-similarity-lcci/
两个(具有不同单词的)文档的交集(intersection)中元素的个数除以并集(union)中元素的个数，就是这两个文档的相似度。例如，{1, 5, 3} 和 {1, 7, 2, 3} 的相似度是 0.4，其中，交集的元素有 2 个，并集的元素有 5 个。给定一系列的长篇文档，每个文档元素各不相同，并与一个 ID 相关联。它们的相似度非常“稀疏”，也就是说任选 2 个文档，相似度都很接近 0。请设计一个算法返回每对文档的 ID 及其相似度。只需输出相似度大于 0 的组合。请忽略空文档。为简单起见，可以假定每个文档由一个含有不同整数的数组表示。
输入为一个二维数组 docs，docs[i] 表示 id 为 i 的文档。返回一个数组，其中每个元素是一个字符串，代表每对相似度大于 0 的文档，其格式为 {id1},{id2}: {similarity}，其中 id1 为两个文档中较小的 id，similarity 为相似度，精确到小数点后 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
最自然的想法当然是对所有文档，计算任意文档的相似度，这样时间复杂度是O(n^2)，没有利用到“稀疏这一特性”。计算相似度用到一个计算式，用符号\text{C}(A)表示集合A内元素的数量。则：
$$
\text{C}(A \cap B) = \text{C}(A) + \text{C}(B) - \text{C}(A \cup B)
$$
于是我们只需要计算两个集合的交集的大小，就可以确定并集的大小。先看暴力的解法，在倒数第二个测试用例超时：
class Solution {
public:
vector<string> computeSimilarities(vector<vector<int>>& docs) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<string> res;
int m = docs.size();
for (int i = 0; i < m - 1; ++i) {
unordered_set<int> us(docs[i].begin(), docs[i].end());
for (int j = i + 1; j < m; ++j) {
int cnt = 0;
for (auto & e : docs[j]) {
if (us.find(e) != us.end()) ++cnt;
}
if (cnt) {
double similar = floor(cnt * 1.0 / (docs[i].size() + docs[j].size() - cnt) * 10000.0 + 0.5) / 10000.0;
string tmp = to_string(similar);
res.push_back(to_string(i) + "," + to_string(j) + ": " + tmp.substr(0, 6));
}
}
}
return res;
}
};
考虑“稀疏”这一特性，我们可以考虑用一个哈希表来记录某个元素究竟出现在哪些集合，然后再用一个哈希表去记录两个集合的交集的元素个数。
class Solution {
public:
vector<string> computeSimilarities(vector<vector<int>>& docs) {
std::ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
vector<string> res;
int m = docs.size();
unordered_map<int, vector<int>> posStore;
map<vector<int>, int> numCount;
for (int i = 0; i < m; ++i) {
for (const auto & e : docs[i]) posStore[e].push_back(i);
}
for (const auto & e : posStore) {
const auto & v = e.second;
int n = v.size();
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
++numCount[{v[i], v[j]}];
}
}
}
for (const auto & e : numCount) {
const int & i = e.first[0];
const int & j = e.first[1];
const int & cnt = e.second;
double similar = floor(cnt * 1.0 / (docs[i].size() + docs[j].size() - cnt) * 10000.0 + 0.5) / 10000.0;
string tmp = to_string(similar);
res.push_back(to_string(i) + "," + to_string(j) + ": " + tmp.substr(0, 6));
}
return res;
}
};
另外这道题还涉及了四舍五入和浮点数精度的确定技巧，另外一种写法（作者da-li-wang）是使用sprintf：
class Solution {
public:
vector<string> computeSimilarities(vector<vector<int>>& docs) {
map<int, vector<int> > content_to_docs;
map<pair<int, int>, int> inters;
for (int i = 0; i < docs.size(); ++i) {
for (auto x : docs[i]) {
content_to_docs[x].push_back(i);
}
}
for (const auto& [c, d] : content_to_docs) {
for (int i = 0; i < d.size(); ++i) {
for (int j = i + 1; j < d.size(); ++j) {
++inters[{d[i], d[j]}];
}
}
}
vector<int> counts;
for (const auto& doc : docs) {
counts.push_back(doc.size());
}
vector<string> res;
for (const auto& [p, inter] : inters) {
int unio = counts[p.first] + counts[p.second] - inter;
double sim = inter * 1.0 / unio;
char s[20];
sprintf(s, "%d,%d: %.4f", p.first, p.second, sim + 1e-9);
res.push_back(string(s, s + 20));
}
return res;
}
};