利用unordered_map维护关联数据

在leetcode上刷339题Evaluate Division(https://leetcode.com/problems/evaluate-division/#/description)时在脑中过了一遍想法,大概是生成26棵树,每棵树又有26个子节点,子节点下方对应其父节点与祖父节点相除的结果.
使用树结构进行存储、再通过问题给出的字母利用DFS进行搜索。
觉得实现起来比较费键盘就没有继续写下去，跑到discuss区看大神的写法。
在ycf303（以下简称y神）的答案中第一次接触到unordered_map这一结构。
unordered_map是C++11特性，利用hash表实现，查找效率极高。
y神代码如下：

 1 class Solution {

 2     public:

 3         vector<double> calcEquation(vector<pair<string, string>> equations,

 4                 vector<double>& values, vector<pair<string, string>> query)

 5         {

 6             unordered_map<string,unordered_map<string, double>> m;

 7             vector<double> res;

 8             for (int i = 0; i < values.size(); ++i)

 9             {

10                 m[equations[i].first].insert(make_pair(equations[i].second,values[i]));

11                 if(values[i]!=0)

12                     m[equations[i].second].insert(make_pair(equations[i].first,1/values[i]));

13             }

14

15             for (auto i : query)

16             {

17                 unordered_set<string> s;

18                 double tmp = check(i.first,i.second,m,s);

19                 if(tmp) res.push_back(tmp);

20                 else res.push_back(-1);

21         }

22         return res;

23     }

24

25     double check(string up, string down,

26             unordered_map<string,unordered_map<string, double>> &m,

27             unordered_set<string> &s)

28     {

29         if(m[up].find(down) != m[up].end()) return m[up][down];

30         for (auto i : m[up])

31         {

32             if(s.find(i.first) == s.end())

33             {

34                 s.insert(i.first);

35                 double tmp = check(i.first,down,m,s);

36                 if(tmp) return i.second*tmp;

37             }

38         }

39         return 0;

40     }

41 };

花了一个多小时对unordered_map进行研究和总结，发现相较于我利用树对题中数据进行存储的方式，unordered_map更加快捷，而且只有实际存在的数据才会进行插入，不用造成不必要的内存开销，是我这种内存强迫症患者的福音。
至于时间复杂度方面，unordered_map查找的时间复杂度O(1)和我的森林相同，但写起来要快捷的多，以后再遇到此类问题需要打表存储，都会尽量使用unordered_map。

巴特西

利用unordered_map维护关联数据

最新文章

热门文章