题目分析

题目通俗易懂小伙伴们不要害怕困难题，先试一试将自己的想法实现出来。

暴力

暴力法是我们直观想到的一种解决方法，我们既然要比较相似度，就要求交集和并集。因此i和j两层循环，然后在循环中计算交集和并集。

算法的**时间复杂度为$O(nm^2)$，空间复杂度为$O(1)$**，其中n为每个文档的平均长度，m为文档个数。

但是n和m的最大值都是500，因此$nm^2 = 1.25e8$会TLE，因此这个算法无法通过所有的测试样例。

#include<iostream>
#include<vector>
#include<unordered_set>
#include<string>

using namespace std;

class Solution {
public:
    vector<string> computeSimilarities(vector<vector<int>>& docs) {
        vector<string> res;
        for (int i = 0; i < docs.size(); i++) {
            for (int j = i + 1; j < docs.size(); j++) {
                int intersectionNum = 0;
                int unionNum = 0;
                cal(docs[i], docs[j], intersectionNum, unionNum);
                if (intersectionNum) {
                    char c[20];
                    sprintf(c, "%d,%d: %.4f", i, j, double(intersectionNum) / unionNum + 1e-9);
                    string s = c;
                    res.push_back(s);
                }
            }
        }
        return res;
    }

    void cal(vector<int>& v1, vector<int>& v2, int& intersectionNum, int& unionNum) {
        unordered_set<int> s;
        for (int x : v1) {
            s.insert(x);
            unionNum++;
        }
        for (int x : v2) {
            if (!s.count(x)) {
                unionNum++;
            }
            else {
                intersectionNum++;
            }
        }
    }
};

哈希表

我们有一些隐含条件没有用到，就是题目中所说的稀疏文档。对于大部分文档来说，它们之间都是不需要计算的，没有重复元素，或者500个元素中只有很少的几个是相似的，那么我们如何节省运算呢？

**我们可以统计每个元素有哪些文档包含，因为比较稀疏，所以文档包含同一个元素的概率非常低。假如10这个元素出现在文档1，文档5，文档8中，那么我们建立一个哈希表，其中键为10，值为{1, 5, 8}的一个数组。这时我们可知1和5有一个相似的元素，1和8有一个相似的元素，5和8有一个相似的元素。这时再用一个数组intersection记录文档i和文档j的相似元素个数。即intersection[1][5]++，intersection[1][8]++，intersection[5][8]++**。
$$similarity = \frac{intersection[i][j]}{(docs[i].size() + docs[j].size() - intersection[i][j])}$$
其中分子是交集元素个数，分母是并集元素个数。这里用到了一部分数学知识，交集数量+并集数量=两个集合数量之和。

在稀疏文档中，文档包含同一个元素的平均个数为常数量级，算法的**时间复杂度为$O(nm)$，在统计每个元素有哪些文档时，用到m x n的空间，在计算文档之间相似元素个数时，用到m x m的空间。因此空间复杂度为$O(m \times max(m, n))$**，其中n为每个文档的平均长度，m为文档个数。

#include<iostream>
#include<vector>
#include<unordered_map>
#include<string>

using namespace std;


class Solution {
public:
    vector<string> computeSimilarities(vector<vector<int>>& docs) {
        int length = docs.size();
        unordered_map<int, vector<int>> wordsInDocs;
        vector<vector<int>> intersection(length, vector<int>(length));
        vector<string> res;
        for (int i = 0; i < length; i++) {
            for (int x : docs[i]) {
                wordsInDocs[x].push_back(i);
            }
        }
        for (auto p : wordsInDocs) {
            vector<int> idx = p.second;
            for (int i = 0; i < idx.size(); i++) {
                for (int j = i + 1; j < idx.size(); j++) {
                    intersection[idx[i]][idx[j]]++;
                }
            }
        }
        for (int i = 0; i < length; i++) {
            for (int j = i + 1; j < length; j++) {
                if (intersection[i][j]) {
                    char c[20];
                    sprintf(c, "%d,%d: %.4f", i, j, double(intersection[i][j]) / (docs[i].size() + docs[j].size() - intersection[i][j]) + 1e-9);
                    string s = c;
                    res.push_back(s);
                }
            }
        }
        return res;
    }
};

刷题总结

哈希表典型的特征是以空间换时间，我们有了哈希表，可以用额外的空间去存储数据的属性，以后查找的时候就不需要遍历数组。哈希表的题目，小伙伴要多多练习。