苏州免费推广的网站,logo网站素材,PHP MySQL 网站开发实例,俄语购物网站建设在之前我们已经学习了解了CSTL当中的string和vector等容器#xff0c;现在我们已经懂得了这些容器提供的接口该如何使用#xff0c;并且了解了这些容器的底层结构。接下来我们在本篇当中将继续学习STL内的容器set与map#xff0c;在此这两个容器与我们之前学习的容器提供的成…在之前我们已经学习了解了CSTL当中的string和vector等容器现在我们已经懂得了这些容器提供的接口该如何使用并且了解了这些容器的底层结构。接下来我们在本篇当中将继续学习STL内的容器set与map在此这两个容器与我们之前学习的容器提供的成员函数以及底层结构有细微的差异。接下来就开始本篇的学习吧 1.顺序式容器与关联式容器
在了解set与map之前我们要先来了解什么是顺序式容器、什么是关联式容器。 前面我们已经接触过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使用介绍
set - C Reference 通过文档就可以看出set的底层其实就是Key搜索场景的结构在此set的声明中还可以看出T就是set底层关键字的类型并且set默认执行小于比较如果不支持或者想按自行的需求走可以自行实现仿函数传给第⼆个模版参数 set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。但⼀般情况下我们都不需要传后两个模版参数。
• set底层是用红黑树实现增删查效率是 O(logN) 迭代器遍历是走的搜索树的中序所以是有序的。
注在此在之前我们已经学习了vector和list等的容器由于因此在set的学习中我们就不再将接口一一的详细学习而是选择重点的和之前学习的容器不同的部分进行学习 2.1.1 构造和迭代器
在set当中由于支持正向和反向的遍历这是由于set的迭代器是双向迭代器这也就使得set支持范围for。遍历时默认的是升序因为底层是⼆叉搜索树迭代器遍历走的是中序。由于set的底层是二叉搜索树这就使得set的迭代器iterator和reserve_iterator等都不支持使用迭代器修改元素内的数据这是由于在二叉搜索树当中随意的修改数据就会破坏二叉搜索树的底层结构因此在set内的迭代器只有读的权限没有写的权限。
并且在没有显示的传comp对应的参数时默认的是key_compare在此你可能会疑惑key_compare是什么在此其实就是仿函数less只不过在set内被重命名了 注在set当中key_type和value_type都是模板类参数T被重命名之后得到的 以上文档中各个构造函数的作用如下所示
set::set - C Reference
// 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_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 以上文档中常用的迭代器如下所示
set - C Reference // 正向迭代器
iterator begin();
iterator end();// 反向迭代器
reverse_iterator rbegin();
reverse_iterator rend(); 2.1.2 增删查
set - C Reference 在set当中提供了以上的成员函数来实现增删查接下来我们就来学习这些成员函数的使用
首先来看在set内提供的插入数据的相关的成员函数只有insert这是由于set底层是二叉搜索树在插入时也要维护住搜索二叉树的结构所以在set当中就没有提供push系列的相关插入函数这就和之前我们学习的序列式容器vector和list等不同。 以上文档中insert各接口的作用如下所示
// 单个数据插⼊如果已经存在则插⼊失败
pairiterator,bool insert (const value_type val);// 列表插⼊已经在容器中存在的值不会插⼊
void insert (initializer_listvalue_type il);// 迭代器区间插⼊已经在容器中存在的值不会插⼊
template class InputIterator
void insert (InputIterator first, InputIterator last);//插入一组值也就是一个initializer_list对象
void insert (initializer_listvalue_type il);使用例如以下示例
#includeiostream
#includeset
using namespace std;
int main()
{// 去重升序排序setint s;// 去重降序排序给⼀个⼤于的仿函数//setint, greaterint s;s.insert(5);s.insert(2);s.insert(7);s.insert(5);//setint::iterator it s.begin();auto it s.begin();while (it ! s.end()){cout *it ;it;}cout endl;// 插⼊⼀段initializer_list列表值已经存在的值插⼊失败s.insert({ 2,8,3,9 });for (auto e : s){cout e ;}cout endl;setstring strset { sort, insert, add };// 遍历string⽐较ascll码⼤⼩顺序遍历的for (auto e : strset){cout e ;}cout endl;
} 接下来来了解set内删除和查找相关函数的使用
set::erase - C Reference set::find - C Reference set::count - C Reference 以上文档中函数各接口的作用如下所示
// 删除⼀个迭代器位置的值
iterator erase (const_iterator position);// 删除valval不存在返回0存在返回1
size_type erase (const value_type val);// 删除⼀段迭代器区间的值
iterator erase (const_iterator first, const_iterator last);// 查找val返回val所在的迭代器没有找到返回end()
iterator find (const value_type val);// 查找val返回Val的个数
size_type count (const value_type val) const; 以上函数使用如下示例所示
#includeiostream
#includeset
using namespace std;
int main()
{setint 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;// 直接删除xint x;cin x;int num s.erase(x);if (num 0){cout x 不存在 endl;}for (auto e : s){cout e ;}cout endl;// 直接查找在利⽤迭代器删除xcin 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;cin x;if (s.count(x)){cout x 在 endl;}else{cout x 不存在 endl;}return 0;
}
在此你可能会疑惑为什么在set内要提供find来实现元素的查找不是直接调用算法库内的find就可以实现要求了吗
在想到这种问题时就先要思考直接调用算法库内的函数有什么缺点还是算法库内的函数是否无法满足要求。就比如之前string内实现自己find就是由于在string当中有的场景下要在string对象内查找字符串算法库内的find就无法实现该功能再比如list内自己实现sort而不去调用算法库内的sort是由于算法库内的sort要求容器对应的迭代器是随机迭代器而由于list的迭代器是双向迭代器就无法满足要求。
在此要解答以上的问题就首先要了解到算法库内的find查找的时间复杂度是O(N)当数据很多时这种查找效率就很低下了因此set内就自己实现了find在此该函数底层根据set底层是二叉搜索树的性质来实现查找使用的查找方式就类似于之前我们实现的二叉搜索树的查找 时间复杂度就为O(logN) 在此在set内删除除了使用以上的方式来删除以外还可以使用以下的两个函数配合来实现指定大小的区间值全部删除
使用到的就是lower_bound和upper_bound 在此itlow_bound返回的是要查找的指定值的迭代器如果对应的set对象内没有指定的值就返回最接近指定值且大于指定值的迭代器 upper_bound返回的是大于要查找的指定值的迭代器如果对应的set对象内没有指定的值就返回最接近指定值且大于指定值的迭代器。
这两个函数这样实现就是为了配合erase在使用迭代器区间删除时迭代器区间是左闭右开的。
例如以下示例
#includeiostream
#includeset
using namespace std;int main()
{setint myset;for (int i 1; i 10; i)myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90for (auto e : myset){cout e ;}cout endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 30auto itlow myset.lower_bound(30);// 返回 60auto itup myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;return 0;
}
以上代码输出结果
再例如以下示例
#includeiostream
#includeset
using namespace std;int main()
{setint myset({ 10 ,20, 35, 40, 50, 65, 70, 80, 90 });for (auto e : myset){cout e ;}cout endl;// 实现查找到的[itlow,itup)包含[30, 60]区间// 返回 30auto itlow myset.lower_bound(30);// 返回 60auto itup myset.upper_bound(60);// 删除这段区间的值myset.erase(itlow, itup);for (auto e : myset){cout e ;}cout endl;return 0;
} 以上代码输出结果 其实在算法库当中也提供了itlow_bound和upper_bound 在此算法库内的函数就可以在vector和list等容器也可以使用不过在使用这两个函数之前要求对象内的元素是有序的这就使得在调用这两个函数之前如果对象内的元素不是有序的就需要先使用sort排序 2.2 multiset和set的差异
multiset - C Reference
set - C Reference
在set当中还提供了multiset其实在此multiset就类似于我们之前二叉搜索树的key搜索场景支持冗余的情况。所以multiset和set的使⽤基本完全类似主要区别点在于multiset支持值冗余那么insert/find/count/erase都围绕着支持值冗余有所差异具体参看下面的样例代码理解。
#includeiostream
#includeset
using namespace std;
int main()
{// 相⽐set不同的是multiset是排序但是不去重multisetint 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给值时会删除所有的xs.erase(x);for (auto e : s){cout e ;}cout endl;return 0;
} 2.3 set使用练习
在了解了set的使用之后接下来我们就来试着通过两道算法题来巩固以上了解的set使用 349. 两个数组的交集 - 力扣LeetCode 通过以上的题目描述就可以看出该算法题要我们实现的是将两个数组的交集返回那么要使用什么样的算法才能实现呢
在此先要将两个数组都排序为升序并且去重之后创建两个下标一开始分别指向两个数组的首元素之后比较两个下标的元素将元素值小的那个数组下标当两个数组下标指向的元素值相同时就将两个下标都并且将值存储到新的数组当中之后一直重复以上的操作直到两个下标中有一个到数组的末尾。 例如以下示例 在以上示例的两个数组排序为升序并且去重之后就变为以下的形式 这时cur1和cur2指向的元素值相同就将对应的元素值存储到新的数组当中接下来继续进行操作 最终就可以得到新数组内的元素为4和9因此原来两个数组的交集为4和9 那么接下来就来实现该算法题的代码
class Solution {
public:vectorint intersection(vectorint nums1, vectorint nums2) {//要将数组nums1和nums2调整为升序而且还要去重就很适合使用setsetint s1{nums1.begin(),nums1.end()};setint s2{nums2.begin(),nums2.end()};//vt内存储s1和s2的交集vectorint vt;auto it1s1.begin();auto it2s2.begin();//遍历s1和s2while(it1!s1.end() it2!s2.end()){if(*it1*it2){it1;}else if(*it1*it2){it2;}else{vt.push_back(*it1);it1;it2;}}return vt;}}; 142. 环形链表 II - 力扣LeetCode 以上的算法题在数据结构当中的链表专题就已经解决过不过之前我们解决该算法题的步骤较为繁琐首先要快慢指针得到快慢指针相交的节点下标之后再定义一个新的指针指向链表的第一个节点之后让新的节点和相交节点同时遍历最终两个指针指向的同一个节点就是入环的第一个节点
那么有什么更加简洁的算法呢
其实在此解决该算法题就可以使用到set首先通过遍历将链表内的节点指针不断地插入到set对象内并且在插入之前通过调用find来查找set对象内是否含有要插入的指针当不存在时才执行插入最终当find的返回值不为迭代器end()时此时的指针就是链表入环的第一个节点指针
以下算法实现代码如下所示
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {setListNode* s;ListNode* curhead;while(cur){auto founds.find(cur);if(found!s.end()){return cur;}else{s.insert(cur);}curcur-next;}return nullptr;}
};
3. map
3.1 map类介绍
map - C Reference 通过文档就可以看出map的底层其实就是key/val搜索场景的结构在此map的声明中还可以看出Key就是map底层关键字的类型T是map底层value的类型并且map默认执行小于比较如果不支持或者想按自行的需求走可以自行实现仿函数传给第三个模版参数 set底层存储数据的内存是从空间配置器申请的如果需要可以自己实现内存池传给第三个参数。⼀般情况下我们都不需要传后两个模版参数。map底层是用红黑树实现增删查改效率是 O(logN) 迭代器遍历是走的中序所以是按key有序顺序遍历的。
3.2 pair类型介绍
pair - C Reference
由于map是key/val搜索场景的结构在map中为了实现key/val就其内部的成员变量就使用到了存储键值对的变量pair在此pair也是一种模板类pair内的成员变量有两个分别是first和second这两个变量的类型是根类模板参数T1和T2确定的
具体的结构如下所示 pair::pair - C Reference
在pair中也提供了以下的构造函数 3.3 map使用介绍
在了解了map的结构我们知道了map适用于key/val的搜索场景那接下来就来了解map中的成员函数 3.3.1 构造函数和迭代器
map::map - C Reference 以上文档中各个构造函数的作用如下所示
// empty (1) ⽆参默认构造
explicit map (const key_compare comp key_compare(),const allocator_type alloc allocator_type());// range (2) 迭代器区间构造
template class InputIteratormap (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_listvalue_type il,const key_compare comp key_compare(),const allocator_type alloc allocator_type()); 在map当中支持正向和反向迭代遍历这是由于map的迭代器是双向迭代器。遍历默认按key的升序顺序因为底层是⼆叉搜索树迭代器遍历走的中序支持迭代器就意味着支持范围formap⽀持修改value数据不⽀持修改key数据这和之前我们学习二叉搜索树key/val场景时一样如果修改关键字数据就会破坏了底层搜索树的结构。 3.3.2 增删查
在map当中和set类似也提供了以下的成员函数来实现对map对象内元素的增、删、查 接下来先来看map内的提供的插入函数insert 注以上的value_type实际上表示的是pairconst key_type,mapped_type在此value_type是被重命名之后得到的。而pair内的模板参数也是被重命名之后的在此key_type实际上表示的是Keymapped_type表示的是T。
以上文档中insert各接口的作用如下所示 //单个数据插入当该数据原来就存在会插入失败当Key相同value不同时也会插入失败
pairiterator,bool insert (const value_type val);//单个数据在指定的迭代器位置插入当当该数据原来就存在会插入失败
iterator insert (iterator position, const value_type val);//迭代器区间插入插入的值原来就存在不会插入
template class InputIterator
void insert (InputIterator first, InputIterator last);//列表插⼊已经在容器中存在的值不会插⼊
void insert (initializer_listvalue_type il); 接下来来了解map内删除和查找相关函数的使用
map::erase - C Reference map::find - C Reference map::count - C Reference 以上文档中函数各接口的作用如下所示
// 查找k返回k所在的迭代器没有找到返回end()
iterator find(const key_type k);// 查找k返回k的个数
size_type count(const key_type k) const;// 删除⼀个迭代器位置的值
iterator erase(const_iterator position);// 删除kk存在返回0存在返回1
size_type erase(const key_type k);// 删除⼀段迭代器区间的值
iterator erase(const_iterator first, const_iterator last); 在此在map中和set一样也提供了lower_bound和upper_bound
// 返回⼤于等k位置的迭代器
iterator lower_bound (const key_type k);
// 返回⼤于k位置的迭代器
const_iterator lower_bound (const key_type k) const;// 返回小于等k位置的迭代器
iterator upper_bound (const key_type k);
// 返回小于等k位置的迭代器
const_iterator upper_bound (const key_type k) const; 使用例如以下示例
#includeiostream
#includemap
using namespace std;
int main()
{// initializer_list构造及迭代遍历mapstring, string dict { {left, 左边}, {right, 右边},{insert, 插入},{ string, 字符串 } };//mapstring, 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种⽅式对⽐之下最后⼀种最⽅便pairstring, string kv1(first, 第一个);dict.insert(kv1);dict.insert(pairstring, 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.3.3 map的数据修改
前⾯提到map支持修改mapped_type 数据不⽀持修改key数据修改关键字数据破坏了底层搜索树的结构。map除了支持修改的⽅式时通过迭代器迭代器遍历时或者find返回key所在的iterator修改map还有⼀个非常重要的修改接口operator[ ]但是operator[ ]不仅仅⽀持修改还⽀持插⼊数据和查数据所以他是⼀个多功能复合接口注注意从内部实现⻆度map这⾥把我们传统说的value值给的是T类型typedef为mapped_type。⽽value_type是红⿊树结点中存储的pair键值对值。日常使用我们还是习惯将这里的T映射值叫做value。
Member types
key_type - The first template parameter (Key)
mapped_type - The second template parameter (T)
value_type - pairconst key_type,mapped_type
在此我们先通过文档中insert函数返回值的描述就可以总结出以下的结论 1、如果key已经在map中插⼊失败则返回⼀个pairiterator,bool对象返回pair对象first是key所在结点的迭代器second是false2、如果key不在在map中插⼊成功则返回⼀个pairiterator,bool对象返回pair对象first是新插⼊key所在结点的迭代器second是true
在此也就是说⽆论插⼊成功还是失败返回pairiterator,bool对象的first都会指向key所在的迭 代器那么也就意味着insert插⼊失败时充当了查找的功能正是因为这⼀点insert可以用来实现operator[] 接下来我们就来看看operator[ ]运算符重载函数内的实现
// operator的内部实现
mapped_type operator[] (const key_type k)
{// 1、如果k不在map中insert会插⼊k和mapped_type默认值同时[]返回结点中存储//mapped_type值的引⽤那么我们可以通过引⽤修改返映射值。所以[]具备了插⼊ 修改功能// 2、如果k在map中insert会插⼊失败但是insert返回pair对象的first是指向key结点的迭代器//返回值同时[]返回结点中存储mapped_type值的引⽤所以[]具备了查找 修改的功能pairiterator, bool ret insert({ k, mapped_type() });iterator it ret.first;return it-second;
} 使用例如以下示例
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{// 利⽤[]插⼊修改功能巧妙实现统计⽔果出现的次数string arr[] { 苹果, 西⽠, 苹果, 西⽠, 苹果, 苹果, 西⽠,苹果, ⾹蕉, 苹果, ⾹蕉 };mapstring, 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;
}
#includeiostream
#includemap
#includestring
using namespace std;
int main()
{mapstring, string dict;dict.insert(make_pair(sort, 排序));// key不存在-插⼊ {insert, string()}dict[insert];// 插⼊修改dict[left] 左边;// 修改dict[left] 左边、剩余;// key存在-查找cout dict[left] endl;return 0;
} 通过以上示例就可以看出相比find与insert在一些场景下直接适用operator就简介许多 3.4 multimap和map的差异
multimap和map的使用基本完全类似主要区别点在于multimap⽀持关键值key冗余那么 insert/find/count/erase都围绕着⽀持关键值key冗余有所差异这⾥跟set和multiset完全⼀样⽐如find时有多个key返回中序第⼀个。其次就是multimap不⽀持[]因为支持key冗余[]就只能⽀持插⼊了不能⽀持修改。 3.5 map使用练习
在了解了map的使用之后接下来我们就来试着通过两道算法题来巩固以上了解的map使用
138. 随机链表的复制 - 力扣LeetCode 数据结构初阶阶段为了控制随机指针我们将拷贝结点链接在原节点的后⾯解决后⾯拷⻉节点还得解下来链接非常⿇烦。这⾥我们直接让{原结点,拷贝结点}建⽴映射关系放到map中控制随机指针会非常简单⽅便这⾥体现了map在解决⼀些问题时的价值完全是降维打击。 实现代码如下所示
/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val _val;next NULL;random NULL;}
};
*/class Solution {
public:Node* copyRandomList(Node* head) {Node* curhead;Node* newhead,*newtail;newheadnewtailnullptr;mapNode*,Node* m;while(cur){if(newheadnullptr){newheadnewtailnew Node(cur-val);}else{newtail-nextnew Node(cur-val);newtailnewtail-next;}m[cur]newtail;curcur-next;} //拷贝节点内randomcurhead;Node* newcurnewhead;while(cur){if(cur-randomnullptr){newcur-randomnullptr;}else{newcur-randomm[cur-random];}curcur-next;newcurnewcur-next;}return newhead;}
}; 692. 前K个高频单词 - 力扣LeetCode 通过以上的题目描述就可以看出本题目我们利⽤map统计出次数以后返回的答案应该按单词出现频率由⾼到低排序有⼀个特殊要求如果不同的单词有相同出现频率按字典顺序排序。
在此有两种方法可以解决该算法题
解决思路1
⽤排序找前k个单词因为map中已经对key单词排序过也就意味着遍历map时次数相同的单词字典序⼩的在前面字典序⼤的在后面。那么我们将数据放到vector中用⼀个稳定的排序就可以实现上面特殊要求但是sort底层是快排通过之前数据结构——排序的学习我们知道快排是不稳定的所以我们要⽤stable_sort他是稳定的其底层排序是归并排序。
实现代码如下所示
class Solution {
public:class compare{public:bool operator()(const pairstring,int x1,const pairstring,int x2){return x1.secondx2.second ;}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int m;for(auto x:words){m[x];}vectorpairstring,int vt(m.begin(),m.end());stable_sort(vt.begin(),vt.end(),compare());vectorstring VT;for(int i0;ik;i){VT.push_back(vt[i].first);}return VT;}
};
解决思路2将map统计出的次数的数据放到vector中排序或者放到priority_queue中来选出前k个。利⽤仿函数强行控制次数相等的字典序⼩的在前面。
实现代码如下所示
class Solution {
public:class compare{public:bool operator()(const pairstring,int x1,const pairstring,int x2){return x1.secondx2.second || (x1.secondx2.second x1.firstx2.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring,int m;for(auto x:words){m[x];}vectorpairstring,int vt(m.begin(),m.end());sort(vt.begin(),vt.end(),compare());vectorstring VT;for(int i0;ik;i){VT.push_back(vt[i].first);}return VT;}
}; class Solution {
public:struct Compare {bool operator()(const pairstring, int x,const pairstring, int y) const {// 要注意优先级队列底层是反的⼤堆要实现⼩于⽐较所以这⾥次数相等想要字典序⼩的在前⾯要⽐较字典序⼤的为真return x.second y.second ||(x.second y.second x.first y.first);}};vectorstring topKFrequent(vectorstring words, int k) {mapstring, int countMap;for (auto e : words) {countMap[e];}// 将map中的单词次数放到priority_queue中仿函数控制⼤堆次数相同按照字典序规则排序priority_queuepairstring, int, vectorpairstring, int, Compare p(countMap.begin(), countMap.end());vectorstring strV;for (int i 0; i k; i){strV.push_back(p.top().first);p.pop();}return strV;}
}; 以上就是本篇的全部内容了希望能得到你的点赞和收藏 ❤️
