【C++】map和set的使用
目录
2.1 set和multiset参考文档 - C++ Reference
练习：2.8 349. 两个数组的交集 - 力扣（LeetCode）
2.9 142. 环形链表 II - 力扣（LeetCode）
3.1 map和multimap参考文档- C++ Reference
3.10 138. 随机链表的复制 - 力扣（LeetCode）
3.11 692. 前K个高频单词 - 力扣（LeetCode）
1. 序列式容器和关联式容器
前面我们已经接触过STL中的部分容器如：string、vector、list、deque、array、forward_list等，这些容器统称为序列式容器，因为逻辑结构为线性序列的数据结构，两个位置存储的值之间一般没有紧密的关联关系，比如交换一下两个数据，它依旧是序列式容器。顺序容器中的元素是按他们在容器中的存储位置来顺序保存和访问的。
关联式容器也是用来存储数据的，与序列式容器不同的是，关联式容器逻辑结构通常是非线性结构，两个位置有紧密的关联关系，交换一下两个数据，它数据间的逻辑关系被破坏了，存储结构就被破坏了。关联式容器中的元素是按关键字来保存和访问的。关联式容器有map/set系列和unordered_map/unordered_set系列。
本文章讲解的map和set底层是红黑树，红黑树是一颗平衡二叉搜索树（红黑树后文详细说明）。set是之前二叉树文章中讲过的key搜索场景的结构，map是key/value搜索场景的结构。
2. set系列的使用
2.1 set和multiset参考文档
<set> - C++ Reference
2.2 set类的介绍
• set的声明如下，T就是set底层关键字的类型（其实这里当年命名时，key-value的概念并不明晰，所以命名为T）
• set默认要求T支持小于比较,数据小的放在二叉搜索树的左边，大的数据放在二叉搜索树的右边，如果不支持或者想按自己的需求走可以自行实现仿函数传给第二个模版参数。
• set底层存储数据的内存是从空间配置器申请的，如果需要可以自己实现内存池，传给第三个参数。
• 一般情况下，我们都不需要传后两个模版参数。
• set底层是用红黑树实现，增删查效率是O(logN)，迭代器遍历是走的搜索树的中序，因为所以是有序的，并且因为set支持的是小于比较，所以中序遍历的结果是递增的。
• 前面部分我们已经学习了vector/list等容器的使用，STL容器接口设计，高度相似，所以这里我们就不再一个接口一个接口的介绍，而是挑比较重要的接口进行介绍。
template < class T, // set::key_type/value_type class Compare = less<T>, // set::key_compare/value_compare class Alloc = allocator<T> // set::allocator_type > class set;2.3 set的构造和迭代器
set的构造我们关注以下几个接口即可。
set的支持正向和反向迭代遍历，因为底层是二叉搜索树，迭代器遍历走的中序，所以遍历默认按升序顺序。
支持迭代器就意味着支持范围for，但是set的iterator和const_iterator都不支持通过迭代器修改数据，因为修改关键字数据，就会破坏底层搜索树的结构。
// empty (1) 无参默认构造 explicit set(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> set(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type()); // copy (3) 拷贝构造 set(const set& x); // initializer list (5) initializer 列表构造 set(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是一个双向迭代器 iterator->a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();2.4 set的增删查
set的增删查关注以下几个接口即可：
Member types key_type->The first template parameter(T) value_type->The first template parameter(T) // 单个数据插入，如果已经存在则插入失败 pair<iterator, bool> insert(const value_type& val); // 列表插入，已经在容器中存在的值不会插入 void insert(initializer_list<value_type> il); // 迭代器区间插入，已经在容器中存在的值不会插入 template <class InputIterator> void insert(InputIterator first, InputIterator last); // 查找val，返回val所在的迭代器，没有找到返回end() iterator find(const value_type& val); // 查找val，返回Val的个数 size_type count(const value_type& val) const; // 删除一个迭代器位置的值 iterator erase(const_iterator position); // 删除val，val不存在返回0，存在返回1 size_type erase(const value_type& val); // 删除一段迭代器区间的值 iterator erase(const_iterator first, const_iterator last); // 返回大于等val位置的迭代器 iterator lower_bound(const value_type& val) const; // 返回大于val位置的迭代器 iterator upper_bound(const value_type& val) const;2.5 insert和迭代器遍历使用样例：
首先对于set来说，实际上分为multiset与set两种，set不允许key值重复，multiset允许，所以set插入时，如果插入的值，容器内已经有了，那么就不会再插入，也就是说set中的每一个值都是独一无二的。
所以当我们向set中插入一串数据时，重复的数不再插入，就可以起到去重的效果，并且根据底层二叉搜索树的特性加上迭代器中序遍历的设计，最后set容器就起到去重加排序的效果。
#include<iostream> #include<set> using namespace std; int main() { // 去重+升序排序 set<int> s; // 去重+降序排序（给一个大于的仿函数） //set<int, greater<int>> s; s.insert(5); s.insert(2); s.insert(7); s.insert(5); //set<int>::iterator it = s.begin(); auto it = s.begin(); while (it != s.end()) { // error C3892: “it”: 不能给常量赋值 // *it = 1; cout << *it << " "; ++it; } cout << endl; // 插入一段initializer_list列表值，已经存在的值插入失败 s.insert({ 2,8,3,9 }); for (auto e : s) { cout << e << " "; } cout << endl; set<string> strset = { "sort", "insert", "add" }; // 遍历string比较ascll码大小顺序遍历的 for (auto& e : strset) { cout << e << " "; } cout << endl; }2.6 find和erase使用样例：
set中find的查找是基于红黑树的结构本身的特性查找的，因此复杂度为
,比起算法库中的查找效率还高。
set的删除是先按照红黑树查找到对应的数据，然后删除，为了与multiset对应，erase会返回成功删除的数据个数，不过set不允许冗余，实际上erase只会有0和1两个结果，如果set内中没有目标数据，就会返回0。
同样的，当set删除之后迭代器也会出现野指针或者指向位置变化等情况，这也叫做迭代器失效，VS下如果继续使用已失效的迭代器，程序就会报错。
#include<iostream> #include<set> using namespace std; int main() { set<int> s = { 4,2,7,2,8,5,9 }; for (auto e : s) { cout << e << " "; } cout << endl; // 删除最小值 s.erase(s.begin()); for (auto e : s) { cout << e << " "; } cout << endl; // 直接删除x int x; cin >> x; int num = s.erase(x); if (num == 0) { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 直接查找在利用迭代器删除x cin >> x; auto pos = s.find(x); if (pos != s.end()) { s.erase(pos); } else { cout << x << "不存在！" << endl; } for (auto e : s) { cout << e << " "; } cout << endl; // 算法库的查找 O(N) auto pos1 = find(s.begin(), s.end(), x); // set自身实现的查找 O(logN) auto pos2 = s.find(x); // 利用count间接实现快速查找 cin >> x; if (s.count(x)) { cout << x << "在！" << endl; } else { cout << x << "不存在！" << endl; } return 0; } 2.7 multiset和set的差异
multiset和set的使用基本完全类似，主要区别点在于multiset支持值冗余，那么insert/find/count/erase都围绕着支持值冗余有所差异
相比set不同的是，multiset只是排序，但是不去重
相比set不同的是，multiset中数据可能会存在多个，但是find查找时，只会返回红黑树中按照中序遍历找到的第一个（返回其他位置的数据没有太大的意义，返回第一个可以通过迭代器找到后续所有的数据）
相比set不同的是，count会返回数据存在的实际个数
相比set不同的是，erase给值时会删除所有的x，并且返回删除的数据个数（不再只有0和1）
#include<iostream> #include<set> using namespace std; int main() { // 相比set不同的是，multiset是排序，但是不去重 multiset<int> s = { 4,2,7,2,4,8,4,5,4,9 }; auto it = s.begin(); while (it != s.end()) { cout << *it << " "; ++it; } cout << endl; // 相比set不同的是，x可能会存在多个，find查找中序的第一个 int x; cin >> x; auto pos = s.find(x); while (pos != s.end() && *pos == x) { cout << *pos << " "; ++pos; } cout << endl; // 相比set不同的是，count会返回x的实际个数 cout << s.count(x) << endl; // 相比set不同的是，erase给值时会删除所有的x s.erase(x); for (auto e : s) { cout << e << " "; } cout << endl; return 0; }2.8.lower_bound和upper_bound
lower_bound（X）会返回指向满足>=X条件的第一个迭代器，upper_bound（X）会返回指向满足>X条件的第一个迭代器，因此当我们要删除一段区间时，如[30,60],我们就可以lower_bound（30）和upper_bound（60），需要注意的容器中迭代器的范围都是左闭右开的，因此这里我们upper_bound（60），返回的指向大于60的迭代器正好可以作为右开区间。
#include<iostream> #include<set> using namespace std; int main() { std::set<int> myset; for (int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90 for (auto e : myset) { cout << e << " "; } cout << endl; // 实现查找到的[itlow,itup)包含[30, 60]区间 // 返回 >= 30 auto itlow = myset.lower_bound(30); // 返回 > 60 auto itup = myset.upper_bound(60); // 删除这段区间的值 myset.erase(itlow, itup); for (auto e : myset) { cout << e << " "; } cout << endl; return 0; }练习：
2.8 349. 两个数组的交集 - 力扣（LeetCode）
这题求两个数组的交集，因为要求输出结果是唯一的，所以我们不能直接使用原数组（如果原数组中有重复值，那么求交集，结果数组中也会出现重复数），所以这里我们需要使用set进行数据去重，并且使用set之后，数据成递增排序。
那么根据数据成递增排序，我们就可以同时遍历两个数组，当迭代器遇到相等的数据，迭代器++，数据不同，我们将指向较小数据的迭代器it1++，因为数组递增，另一个数组中it2之后的数据都是比it1大的，一定不会出现相交的情况。
class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1(nums1.begin(), nums1.end()); set<int> s2(nums2.begin(), nums2.end()); // 因为set遍历是有序的，有序值，依次比较 // 小的++，相等的就是交集 vector<int> ret; auto it1 = s1.begin(); auto it2 = s2.begin(); while (it1 != s1.end() && it2 != s2.end()) { if (*it1 < *it2) { it1++; } else if (*it1 > *it2) { it2++; } else { ret.push_back(*it1); it1++; it2++; } } return ret; } };2.9 142. 环形链表 II - 力扣（LeetCode）
数据结构初阶阶段，我们通过证明一个指针从头开始走一个指针从相遇点开始走，会在入口点相遇，理解证明都会很麻烦。
这里我们使用set查找记录解决非常简单方便，我们每遍历一个节点，先查看该节点地址是否在set中，如果不在，我们将节点的地址插入set中(不能插入节点存储的数据，因为数据可能会出现重复的)；如果节点的地址在set中，那么就说明该节点之前遍历过了，该节点就是链表成环的第一个节点。
这里体现了set在解决一些问题时的价值，完全是降维打击。
class Solution { public: ListNode* detectCycle(ListNode* head) { set<ListNode*> s; ListNode* cur = head; while (cur) { auto ret = s.insert(cur); if (ret.second == false) return cur; cur = cur->next; } return nullptr; } };3. map系列的使用
3.1 map和multimap参考文档
<map> - C++ Reference
3.2 map类的介绍
map的声明如下，Key就是map底层关键字的类型，T是map底层value的类型，set默认要求Key支持小于比较，如果不支持或者需要的话可以自行实现仿函数传给第二个模版参数，map底层存储数据的内存是从空间配置器申请的。一般情况下，我们都不需要传后两个模版参数。map底层是用红黑树实现，增删查改效率是 O(logN)，迭代器遍历是走的中序，所以是按key有序顺序遍历的。
template < class Key, // map::key_type class T, // map::mapped_type class Compare = less<Key>, // map::key_compare class Alloc = allocator<pair<const Key, T> > // //map::allocator_type > class map;3.3 pair类型介绍
之前介绍key_value模型时，key与value是定义在类内的两个变量，而map底层的红黑树节点中的数据，使用pair以pair<Key, T>存储键值对数据。
pair也是作为模版实现的，使用时我们需要传入两个类型，对应第一个值与第二个值，通过obj.first与obj.second可以分别取出第一个值与第二个值。
pair的设计可以帮助我们在函数返回的时候返回两个不同的值或者两个不同类型的值。
typedef pair<const Key, T> value_type; template <class T1, class T2> struct pair { typedef T1 first_type; typedef T2 second_type; T1 first;//第一个值 T2 second;//第二个值 pair() : first(T1()), second(T2()) {} pair(const T1& a, const T2& b) : first(a), second(b) {} template<class U, class V> pair(const pair<U, V>& pr) : first(pr.first), second(pr.second) {} }; template <class T1, class T2> inline pair<T1, T2> make_pair(T1 x, T2 y) { return (pair<T1, T2>(x, y)); } int main() { pair<int, int> example(3, 2025); cout << example.first << endl;//.first取出第一个元素 cout << example.second << endl;//.second取出第二个元素 return 0; }3.4 map的构造
map的构造我们关注以下几个接口即可。
map的支持正向和反向迭代遍历，遍历默认按key的升序顺序，因为底层是二叉搜索树，迭代器遍历走的中序；支持迭代器就意味着支持范围for，map支持修改value数据，不支持修改key数据，因为key还是作为关键字数据，修改关键字数据，会破坏底层搜索树的结构。
// empty (1) 无参默认构造 explicit map(const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // range (2) 迭代器区间构造 template <class InputIterator> map(InputIterator first, InputIterator last, const key_compare& comp = key_compare(), const allocator_type & = allocator_type()); // copy (3) 拷贝构造 map(const map& x); // initializer list (5) initializer 列表构造 map(initializer_list<value_type> il, const key_compare& comp = key_compare(), const allocator_type& alloc = allocator_type()); // 迭代器是一个双向迭代器 iterator->a bidirectional iterator to const value_type // 正向迭代器 iterator begin(); iterator end(); // 反向迭代器 reverse_iterator rbegin(); reverse_iterator rend();#include<map> using namespace std; int main() { //默认构造 map<string, string> dict1; //使用列表初始化构造 map<string,string> dict2 = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } }; //拷贝构造 map<string, string> dict3(dict2); //迭代器区间构造 map<string, string> dict4(dict2.begin(), dict2.end()); return 0; }3.5 map的增删查
map的增删查关注以下几个接口即可：
map增接口，插入的pair键值对数据，跟set所有不同，但是查和删的接口只用关键字key跟set是完全类似（value的值是否相同不会影响pair的数据的插入，但是key必须保持不同）；不过map的find返回iterator，不仅仅可以确认key在不在，还找到通过pair结构找到key映射的value，同时通过迭代还可以修改value。
Member types key_type->The first template parameter(Key) mapped_type->The second template parameter(T) value_type->pair<const key_type, mapped_type> // 单个数据插入，如果已经key存在则插入失败,key存在相等value不相等也会插入失败 pair<iterator, bool> insert(const value_type& val); // 列表插入，已经在容器中存在的值不会插入 void insert(initializer_list<value_type> il); // 迭代器区间插入，已经在容器中存在的值不会插入 template <class InputIterator> void insert(InputIterator first, InputIterator last); // 查找k，返回k所在的迭代器，没有找到返回end() iterator find(const key_type& k); // 查找k，返回k的个数 size_type count(const key_type& k) const; // 删除一个迭代器位置的值 iterator erase(const_iterator position); // 删除k，k存在返回0，存在返回1 size_type erase(const key_type& k); // 删除一段迭代器区间的值 iterator erase(const_iterator first, const_iterator last); // 返回大于等k位置的迭代器 iterator lower_bound(const key_type& k); // 返回大于k位置的迭代器 const_iterator lower_bound(const key_type& k) const;3.6 map的数据修改
前面提到map支持修改mapped_type 数据，不支持修改key数据，因为修改关键字数据，破坏了底层搜索树的结构。
map第一个支持修改的方式是通过迭代器，迭代器遍历时或者find返回key所在的iterator修改。使用find时，我们传入对应关键值key在容器中搜索，找到对应的关键字，我们返回对应的迭代器，需要注意的是这个迭代器指向的是一个pair类型对象，我们pair的.first和.second来访问对应数据。
Member types key_type->The first template parameter(Key) mapped_type->The second template parameter(T) value_type->pair<const key_type, mapped_type> // 查找k，返回k所在的迭代器，没有找到返回end()，如果找到了通过iterator可以修改key对应的 //mapped_type值 iterator find(const key_type& k);map还有一个非常重要的修改接口operator[]，但是与之前所介绍不同的是map的operator[]不仅仅支持修改，还支持插入数据和查找数据，他是一个多功能复合接口（因为map容器我们根据key查找数据，key不能改变，而value可以改变，因此operator[]接口如果可以查到数据的同时可以修改对应的value就非常有价值）。
3.6.1关于operator[]底层实现的特殊说明
要理解operator[]复合功能实现之前，需要先介绍一下map的insert。
// 文档中对insert返回值的说明
The single element versions (1) return a pair, with its member pair::first
set to an iterator pointing to either the newly inserted element or to the
element with an equivalent key in the map.The pair::second element in the pair
is set to true if a new element was inserted or false if an equivalent key
already existed.
根据文档的意思，insert插入一个pair<key, T>对象会出现以下两种情况
1、如果key已经在map中，插入失败（map是根据key查找的，T不同不影响），则返回一个pair<iterator,bool>对象，返回pair对象的first是key所在结点的迭代器，second是false，表明插入失败
2、如果key不在map中，插入成功，则返回一个pair<iterator,bool>对象，返回pair对象
first是新插入key所在结点的迭代器，second是true，表示插入成功
也就是说无论插入成功还是失败，返回pair<iterator,bool>对象的first都会指向key所在的迭
代器，那么也就意味着insert插入失败时充当了查找的功能（注：如果不确定map中释放有对应key，不推荐insert来查找的，因为一旦没有对应key，insert就会插入key,污染原来的数据），正是因为这一点，insert可以用来实现operator[]，
需要注意的是这里有两个pair，不要混淆了，一个是map底层红黑树节点中存的pair<key, T>，另一个是insert返回值pair<iterator, bool>。
pair<iterator, bool> insert(const value_type& val);3.6.2关于operator[]底层实现的具体说明
operator[]底层封装了insert,通过insert插入对应的数据，然后insert返回pair<iterator, bool>，取到对应的数据，然后将通过value的引用返回，我们就可以在外部通过key修改容器内部的value.
详细情况分为以下两种：
1、如果k不在map中，insert会插入k和mapped_type默认值，同时[]返回结点中存储
mapped_type值的引用，那么我们可以通过引用修改返映射值。所以[]具备了插入 + 修改功能
2、如果k在map中，insert会插入失败，但是insert返回pair对象的first是指向key结点的迭代器，返回值同时[]返回结点中存储mapped_type值的引用，所以[]具备了查找 + 修改的功能。
总的来说，我们就可以以operator[]，通过key修改对应的value了。
需要注意从内部实现角度，map这里把我们传统说的value值，给的是T类型，typedef为
mapped_type。而value_type是红黑树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
mapped_type& operator[] (const key_type& k); // operator的内部实现 mapped_type& operator[] (const key_type& k) { pair<iterator, bool> ret = insert({ k, mapped_type() }); iterator it = ret.first; return it->second; }3.7 构造遍历及增删查使用样例
#include<iostream> #include<map> using namespace std; int main() { // initializer_list构造及迭代遍历 map<string, string> dict = { {"left", "左边"}, {"right", "右边"}, {"insert", "插入"},{ "string", "字符串" } }; //map<string, string>::iterator it = dict.begin(); auto it = dict.begin(); while (it != dict.end()) { //cout << (*it).first <<":"<<(*it).second << endl; // map的迭代基本都使用operator->,这里省略了一个-> // 第一个->是迭代器运算符重载，返回pair*，第二个箭头是结构指针解引用取pair数据 //cout << it.operator->()->first << ":" << it.operator->()-> second << endl; cout << it->first << ":" << it->second << endl; ++it; } cout << endl; // insert插入pair对象的4种方式，对比之下，最后一种最方便 pair<string, string> kv1("first", "第一个"); dict.insert(kv1); dict.insert(pair<string, string>("second", "第二个")); dict.insert(make_pair("sort", "排序")); dict.insert({ "auto", "自动的" }); // "left"已经存在，插入失败 dict.insert({ "left", "左边，剩余" }); // 范围for遍历 for (const auto& e : dict) { cout << e.first << ":" << e.second << endl; } cout << endl; string str; while (cin >> str) { auto ret = dict.find(str); if (ret != dict.end()) { cout << "->" << ret->second << endl; } else { cout << "无此单词，请重新输入" << endl; } } // erase等接口跟set完全类似，这里就不演示讲解了 return 0; }3.8 map的迭代器和[]功能样例：
#include<iostream> #include<map> #include<string> using namespace std; int main() { // 利用find和iterator修改功能，统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // 先查找水果在不在map中 // 1、不在，说明水果第一次出现，则插入{水果, 1} // 2、在，则查找到的节点中水果对应的次数++ auto ret = countMap.find(str); if (ret == countMap.end()) { countMap.insert({ str, 1 }); } else { ret->second++; } } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; } #include<iostream> #include<map> #include<string> using namespace std; int main() { // 利用[]插入+修改功能，巧妙实现统计水果出现的次数 string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" }; map<string, int> countMap; for (const auto& str : arr) { // []先查找水果在不在map中 // 1、不在，说明水果第一次出现，则插入{水果, 0}，同时返回次数的引用， ++一下就变成1次了 // 2、在，则返回水果对应的次数++ countMap[str]++; } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; return 0; }#include<iostream> #include<map> #include<string> using namespace std; int main() { map<string, string> dict; dict.insert(make_pair("sort", "排序")); // key不存在->插入 {"insert", string()} dict["insert"]; // 插入+修改 dict["left"] = "左边"; // 修改 dict["left"] = "左边、剩余"; // key存在->查找 cout << dict["left"] << endl; return 0; }3.9 multimap和map的差异
multimap和map的使用基本完全类似，主要区别点在于multimap支持关键值key冗余，那么
insert/find/count/erase都围绕着支持关键值key冗余有所差异，这里跟set和multiset完全一样，
比如find时，有多个key，返回中序第一个。
其次就是multimap不支持[]，因为支持key冗余，[]就只能支持插入了，不能支持修改，不然无法确定具体修改的是哪个value值。
练习
3.10 138. 随机链表的复制 - 力扣（LeetCode）
对于这一道题，数据结构初阶阶段，为了控制随机指针，我们将拷贝结点链接在原节点的后面解决，后面拷贝节点还得解下来链接，非常麻烦。【初阶数据结构】链表经典OJ（8道）_oj题-ZEEKLOG博客
这里我们直接让{原结点,拷贝结点}建立映射关系放到map中，原链表中随机指针指向对应原链表中节点，由于{原结点,拷贝结点}映射关系，我们根据原链表指向关系，我们拷贝节点指向对应映射的节点
这样控制随机指针会非常简单方便，这里体现了map在解决一些问题时的价值，完全是降维打击。
class Solution { public: Node* copyRandomList(Node* head) { map<Node*, Node*> nodeMap; Node* copyhead = nullptr, * copytail = nullptr; Node* cur = head; while (cur) { if (copytail == nullptr) { copyhead = copytail = new Node(cur->val); } else { copytail->next = new Node(cur->val); copytail = copytail->next; } // 原节点和拷贝节点map kv存储 nodeMap[cur] = copytail; cur = cur->next; } // 处理random cur = head; Node* copy = copyhead; while (cur) { if (cur->random == nullptr) { copy->random = nullptr; } else { copy->random = nodeMap[cur->random]; } cur = cur->next; copy = copy->next; } return copyhead; } };3.11 692. 前K个高频单词 - 力扣（LeetCode）
本题目我们利用map根据对应单词统计对应的出现次数以后，返回的答案还应该按单词出现频率由高到低排序，但是这里有一个特殊要求，如果不同的单词有相同出现频率，按字典顺序排序。
解决思路1：
用排序找前k个单词，因为map中已经对key单词排序过，也就意味着遍历map时，次数相同的单词，字典序小的在前面，字典序大的在后面。那么我们将数据放到vector中用一个稳定的排序就可以实现上面特殊要求，但是sort底层是快排，是不稳定的，所以我们要用stable_sort，他是稳定的。
class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { return x.second > y.second; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for (auto& e : words) { countMap[e]++; } vector<pair<string, int>> v(countMap.begin(), countMap.end()); // 仿函数控制降序 stable_sort(v.begin(), v.end(), Compare()); //sort(v.begin(), v.end(), Compare()); // 取前k个 vector<string> strV; for (int i = 0; i < k; ++i) { strV.push_back(v[i].first); } return strV; } };解决思路2：
将map统计出的次数的数据放到vector中排序，或者放到priority_queue中来选出前k个。利用仿函数强行控制次数相等的，字典序小的在前面。
class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { return x.second > y.second || (x.second == y.second && x.first < y.first);; } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for (auto& e : words) { countMap[e]++; } vector<pair<string, int>> v(countMap.begin(), countMap.end()); // 仿函数控制降序,仿函数控制次数相等，字典序小的在前面 sort(v.begin(), v.end(), Compare()); // 取前k个 vector<string> strV; for (int i = 0; i < k; ++i) { strV.push_back(v[i].first); } return strV; } };class Solution { public: struct Compare { bool operator()(const pair<string, int>& x, const pair<string, int>& y) const { // 要注意优先级队列底层是反的，大堆要实现小于比较，所以这里次数相等，想要字典 序小的在前面要比较字典序大的为真 return x.second < y.second || (x.second == y.second && x.first > y.first); } }; vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> countMap; for (auto& e : words) { countMap[e]++; } // 将map中的<单词，次数>放到priority_queue中，仿函数控制大堆，次数相同按照字典 序规则排序 priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> p(countMap.begin(), countMap.end()); vector<string> strV; for (int i = 0; i < k; ++i) { strV.push_back(p.top().first); p.pop(); } return strV; } };
