1. 简介
- unordered_map是一种key-value关联容器,可以高效地通过单个key值查找对应的value
- key值是唯一的
- unordered_map不按序存储,其底层实现是哈希表,根据key的哈希值,将元素存在特定位置,所以根据key查找value时非常高效,时间复杂度为O(1)
2. 使用
需要使用哈希表的场景都可以使用一个unordered_map来实现
3. unordered_map排序
如何对无序的unordered_map进行排序?
使用pair容器,每个pair存一对键值对,作为元素放入一个vector,重写sort()的compare函数,就可以对vector进行排序了。
具体实现(针对 [HOT100]347前k个高频元素这道题):
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> m;
for(auto i:nums){
if(m.count(i))
m[i]++;
else
m[i]=1;
}
vector<pair<int,int>> v;
for(auto i:m){
v.push_back(i);
}
sort(v.begin(),v.end(),[](auto &p1,auto &p2){return p1.second>p2.second;});
vector<int>re;
for(int i=0;i<k;i++)
{
re.push_back(v[i].first);
}
return re;
}
};