目录前言一、map结构的实际应用1.1 随机链表的复制1.2 前K个高频单词1.2.1 稳定排序与非稳定排序1.3 单词识别结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、map结构的实际应用1.1 随机链表的复制该题目在数据结构专栏的文章有过提及不过当时是用C写的随机链表的赋值随机链表的复制/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){if(headnullptr)returnnullptr;mapNode*,Node*nodeMap;Node*copyheadnullptr;Node*copytailnullptr;Node*curhead;//创建新链表结构while(cur){Node*copynewNode(cur-val);if(copytailnullptr){//第一个结点初始化头尾copyheadcopytailcopy;}else{//新节点在尾部copytail-nextcopy;copytailcopy;}//记录原结点 - 新结点的映射nodeMap.insert({cur,copy});curcur-next;}//复制random指针curhead;Node*copycopyhead;while(cur){if(cur-randomnullptr){copy-randomnullptr;}else{//通过map查找原结点random对应的新结点copy-randomnodeMap[cur-random];}curcur-next;copycopy-next;}returncopyhead;}};解法核心思路红黑树std::map实现键值映射用std::map建立「原节点 → 新节点」的一一映射解决random指针无法直接复制的问题分两步遍历第一次遍历创建所有新节点构建新链表的next结构同时用map记录原节点和新节点的对应关系第二次遍历通过map的键值查找把原节点的random指针映射到新节点的random指针。核心逻辑map的有序性对本题无意义但它的 “键唯一 可查找” 特性刚好满足 “原节点→新节点” 的映射需求。要点补充map.insert({cur, copy})的作用把 “原节点cur” 作为键“对应的新节点copy” 作为值存入map。这一步是为了后续能通过 “原节点的指针” 快速找到 “对应的新节点”。nodeMap[cur-random]的本质这是std::map的查找操作底层是红黑树的遍历时间复杂度为O(logn)。比如原节点cur的random指向节点A通过nodeMap[A]就能找到新链表中对应的节点A’从而给新节点的random赋值。时间复杂度O(nlogn)两次遍历链表O(n)每次map的插入 / 查找操作O(logn)红黑树的高度总复杂度n×O(logn)O(nlogn)。空间复杂度O(n)map存储了n个 “原节点→新节点” 的映射占用O(n)空间新链表本身占用O(n)空间题目要求深拷贝这部分空间不计入 “额外空间”。在绝大多数场景下会用 “哈希表” 代指 “键值映射结构”不会严格区分底层是红黑树还是哈希表。以后看到有人明明用了红黑树的底层却也说是哈希表也不会困惑了1.2 前K个高频单词前K个高频单词要点补充注意这里map统计次数之后虽然map本身就是排好序的但是内部是对string不是对次数排序但是若要再使用mapint, string sortMap也是不对的map 的 key 必须唯一不允许重复。当多个单词出现相同频率时比如示例 1 中 “i” 和 “love” 频率都是 2先插入 {2, “i”}此时 sortMap 中 key2 存在。再插入 {2, “love”}因为 key2 已存在会直接覆盖之前的 “i”导致数据丢失。最终 sortMap 只会保留最后一个插入的同频率单词无法得到完整的结果。mapint, string sortMap不能使用但是multimapint, string sortMap是可以的。multimapint, string允许同一个 Key频率对应多个 Value单词所有同频率单词都能完整存储不会丢失数据。但是这样也是不建议的map和set顺便排序是可以的但是真的比起来在大量数据的情况下二者的效率是不如vector sort的如上图这种看似正确的写法最终也是错误的 排序逻辑完全不符合题目要求根本原因pairstring, int的比较优先级错误直接用greater会调用pairstring, int()比较大小pairstring, int 的默认比较规则是先比较第一个元素字符串字典序字典序小的排前面只有当第一个元素相等时才会比较第二个元素int数值。而用 greaterpairstring, int 会把这个逻辑反过来先按字符串字典序降序排序再按 int 数值降序 排序。这和题目要求的排序规则完全相反题目要求先按频率int降序频率相同再按字符串字典序升序具体例子验证以示例 1 为例输入words [i, love, leetcode, i, love, coding]countMapmapstring, int天然按字符串字典序升序存储{coding:1, i:2, leetcode:1, love:2}构造vectorpairstring, int v后顺序和 countMap 一致[{coding,1}, {i,2}, {leetcode,1}, {love,2}]执行sort(v.begin(), v.end(), greaterpairstring, int)后按字符串字典序降序排列结果变为[{love,2}, {leetcode,1}, {i,2}, {coding,1}]取前 k2 个单词[love, leetcode]但正确结果应该是[i, love]完全不符合要求。基于这样的原因这里就要自己实现一个仿函数来控制比较的逻辑可以看到依旧是没有通过全部测试用例的但是这次是111个测试用例中通过了31个第32个没有通过而且可以看到没过的用例是某两个词的顺序和正确的结果交换了原因是没有处理不同的单词有相同出现频率 按字典顺序排序这种情况这里也是可以通过打印验证的LeetCode有一个好处就是其打印的东西是可以看见的把需要打印的代码写上提交一下就可以了这里是有多种解决方案的1.2.1 稳定排序与非稳定排序首先补充一下几个概念一、什么是「稳定排序」稳定排序如果两个元素的比较键值相等排序后它们的相对位置和排序前保持一致。非稳定排序即使两个元素的比较键值相等排序后它们的相对位置可能被打乱。std::sort 是非稳定排序核心原因和它的实现原理直接相关。二、为什么 std::sort 不稳定1. 底层实现快速排序非稳定为核心C 标准库中std::sort 通常采用 Introsort内省排序主体是快速排序QuickSort快速排序的「分区partition」过程会通过交换元素实现这个交换是「无序」的 —— 即使两个元素的比较键值相等也可能被交换位置打乱原始相对顺序。只有当递归深度过深时会退化为堆排序HeapSort堆排序同样是非稳定排序。仅在数据量极小时会用插入排序稳定但整体仍属于非稳定排序。直观例子假设有一个待排序的数组元素是 (单词, 频率)structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second;}};// 排序前同频率2的 i 在 love 前面vectorpairstring,intv{{i,2},{love,2},{coding,1}};// 仅按频率排序忽略字典序用 sort 排序sort(v.begin(),v.end(),kv_pair())// 非稳定排序的结果可能变成{love,2}, {i,2}, {coding,1}// love 和 i 频率相同但相对位置被打乱了所以此时就有了第一种解决方案算法库中的stable_sort 是稳定排序按「频率降序」排序时同频率元素的相对位置会被保留即保留字典序。前面mapstring, int countMap是有序容器遍历顺序天然是「字符串字典序升序」→ 同频率的单词在 countMap 中已经按字典序排好了。用vectorpairstring, int v(countMap.begin(), countMap.end())构造后vector 里的元素顺序和 countMap 完全一致同频单词保持字典序。此时使用std::stable_sort会保证同频率的 “i” 仍在 “love” 前面。classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second;}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}//mapint, string sortMap;//multimapint, string sortMap;//迭代器区间构造vectorpairstring,intv(countMap.begin(),countMap.end());//默认是升序这里排降序,sort是个函数模板要传对象//sort(v.begin(), v.end(), kv_pair());//稳定的排序stable_sort(v.begin(),v.end(),kv_pair());for(auto[k,v]:v){coutk:vendl;}coutendl;vectorstringret;for(size_t i0;ik;i){ret.push_back(v[i].first);}returnret;}};说一下stable_sort(v.begin(), v.end(), kv_pair());中kv_pair()的底层调用步骤 1创建 kv_pair 临时对象kv_pair() 是结构体的无参构造函数调用会在栈上创建一个 kv_pair 类型的临时对象匿名对象。这个对象没有成员变量仅承载 operator() 这个重载方法。它的生命周期从传入 stable_sort 开始到 stable_sort 执行结束后销毁。步骤 2stable_sort 接收并使用这个函数对象stable_sort 是函数模板其核心签名可简化理解为templateclassRandomIt,classComparevoidstable_sort(RandomIt first,RandomIt last,Compare comp);这里的 Compare 就是 kv_pair 类型comp 是传入的 kv_pair() 临时对象。步骤 3stable_sort 内部调用 comp.operator() 比较元素stable_sort 底层基于归并排序实现排序过程中会不断调用 comp 对象的 operator() 方法完成元素比较每次需要比较两个元素 akv1和 bkv2时会执行comp.operator()(a,b);// 等价于 kv_pair()(a, b)operator() 逻辑是return kv1.second kv2.second;即如果 a 的频率 b 的频率返回 true → a 应该排在 b 前面否则返回 false → b 应该排在 a 前面若频率相等返回 false → stable_sort 会保留原始相对位置这是稳定排序的核心。步骤 4临时对象销毁stable_sort 执行完成后传入的 kv_pair() 临时对象会被自动析构栈上对象出作用域销毁。为什么要传 kv_pair() 而不是 kv_pairkv_pair 是类型名kv_pair() 是创建该类型的临时对象stable_sort 需要的是「可调用的对象」而非类型本身 —— 必须通过 () 构造对象才能让 stable_sort 调用其 operator()。Compare comp 是函数参数而非模板参数作用是接收一个具体的可调用对象需要用这个对象的 operator() 做比较。因此必须传 kv_pair()创建 kv_pair 类型的临时对象而非仅传类型名 kv_pair类型名无法被函数调用方案缺陷强依赖「countMap 是有序容器」的隐含特性如果后续不小心把mapstring, int改成unordered_mapstring, int无序哈希表更高效countMap 的遍历顺序会完全随机此时 stable_sort 保留的「相对位置」也会随机结果直接错误。代码可读性差其他开发者甚至未来的你看代码时会疑惑题目要求「同频按字典序升序」但比较函数里完全没提字典序为什么结果是对的必须追溯到 countMap 的类型、vector 的构造方式、stable_sort 的稳定性才能理解逻辑增加了理解成本。性能略差stable_sort 底层是归并排序时间复杂度虽然也是 O (n log n)但常数更大需要额外空间存储临时数据而 sort 是内省排序快速排序 堆排序效率更高刷题 / 工程中优先选 sort。基于这些缺陷就有了第二种方案由于稳定性是改不了的所以只能改变比较逻辑直接在比较函数中明确写出「频率降序 同频字典序升序」不依赖任何隐含特性代码更健壮、易读classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second||(kv1.secondkv2.secondkv1.firstkv2.first);}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}//mapint, string sortMap;//multimapint, string sortMap;//迭代器区间构造vectorpairstring,intv(countMap.begin(),countMap.end());//默认是升序这里排降序,sort是个函数模板要传对象sort(v.begin(),v.end(),kv_pair());//稳定的排序//stable_sort(v.begin(), v.end(), kv_pair());for(auto[k,v]:v){coutk:vendl;}coutendl;vectorstringret;for(size_t i0;ik;i){ret.push_back(v[i].first);}returnret;}};由于这里数据量不大找最大的前k个还可以考虑用大堆第三套方案classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second||(kv1.secondkv2.secondkv1.firstkv2.first);}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}priority_queuepairstring,int,vectorpairstring,int,kv_pairpq(countMap.begin(),countMap.end());// //打印// for(auto [k,v] : v)// {// cout k : v endl;// }// cout endl;vectorstringret;for(size_t i0;ik;i){ret.push_back(pq.top().first);pq.pop();}returnret;}};这是优先队列大顶堆解法核心是用堆来维护「频率最高 同频字典序最小」的单词顺序直接取前 k 个即可。要点补充priority_queue 在 C 中默认是大顶堆但它的比较器是「小于」逻辑和 sort 相反所以我觉得这个很坑提供方法但是不建议用当 comp(a, b) 返回 true 时a 的优先级比 b 低会被放在 b 的下方。kv1.second kv2.second若 kv1 频率 kv2 频率 → 返回 true → kv1 优先级更低kv2 会被放到堆上方保证频率高的在前。kv1.second kv2.second kv1.first kv2.first若频率相同且 kv1 字典序 kv2 字典序 → 返回 true → kv1 优先级更低kv2 会被放到堆上方保证同频字典序小的在前。priority_queuepairstring, int, vectorpairstring, int, kv_pair pq(countMap.begin(), countMap.end());这里可以直接传kv_pair而不是kv_pair()的原因是priority_queue 的第三个参数是模板参数指定类型而 stable_sort 的第三个参数是函数参数传递对象C 中 priority_queue 的完整模板声明如下templateclassT,classContainervectorT,classComparelessTclasspriority_queue;T队列中存储的元素类型pairstring, intContainer底层存储容器的类型vectorpairstring, intCompare比较器的类型不是比较器对象是kv_pair 这个结构体类型。模板参数的作用是告诉编译器 “用什么类型”而非 “传递一个具体的对象”。因此需要传 kv_pair类型名而非 kv_pair()创建该类型的对象。你可能会问既然只指定了比较器类型 kv_pair那实际做比较的对象从哪来答案是priority_queue 会在构造时自动创建比较器对象当调用priority_queue...,kv_pairpq(countMap.begin(),countMap.end());priority_queue 的构造函数会先默认构造一个 kv_pair 类型的比较器对象调用 kv_pair 的无参构造函数因为 kv_pair 没有自定义构造函数编译器会生成默认的用这个默认创建的比较器对象来调整堆的顺序和 stable_sort 中手动传 kv_pair() 效果完全一致。只有当你的比较器有非默认构造函数比如需要传参数初始化时才需要在构造 priority_queue 时手动传对象。例如// 假设比较器需要一个阈值有带参构造函数structkv_pair{intthreshold;kv_pair(intt):threshold(t){}// 带参构造booloperator()(constautoa,constautob){...}};// 此时需要先创建带参数的比较器对象再传给构造函数kv_paircomp(10);// 创建带参数的对象priority_queue...,kv_pairpq(comp,countMap.begin(),countMap.end());而这里的 kv_pair 是无状态的没有成员变量仅重载了 operator()因此用默认构造的对象即可无需手动传。1.3 单词识别BITKY120 单词识别解题思路读入整行用 getline 读取带空格的完整句子清洗字符遍历每个字符非字母转空格字母统一转小写用 isalpha、tolower统计次数用 stringstream 按空格拆分单词unordered_map 统计每个小写单词出现次数自定义排序把哈希表转为 vector按次数从多到少次数相同按单词字典序从小到大排序格式输出按 单词:次数 逐行打印#includeiostream#includeunordered_map#includevector#includestring#includealgorithm#includesstreamusingnamespacestd;boolcompare(constpairstring,inta,constpairstring,intb){if(a.second!b.second)returna.secondb.second;returna.firstb.first;}intmain(){//1.安全读取整行输入包含空格如果输入为空直接退出程序string s;if(!getline(cin,s))return0;//清洗字符串string cleans;for(autoch:s){//如果不是字母(句号、逗号、空格、感叹号等),统一替换为空格if(!isalpha(ch))cleans ;//是字母强制转小写elsecleanstolower(ch);}//2.裁剪字符串并读入频率unordered_mapstring,intcount;stringstreamss(cleans);string word;//自动按空格分割无视连续空格/首尾空格直接读取纯单词while(ssword)count[word];//3.换容器 自定义排序vectorpairstring,intword_list(count.begin(),count.end());sort(word_list.begin(),word_list.end(),compare);//4.格式化输出for(autoe:word_list)coute.first:e.secondendl;return0;}说一下这道题目的细节点getline(cin, s)读取一整行文字cin s 遇到空格就停止读不完句子if (!getline)处理空输入边界防止程序崩溃这段代码的【核心灵魂】string clean_str;for(charch:s){// 遍历输入的每一个字符// 关键逻辑如果不是字母句号、逗号、空格、感叹号等if(!isalpha(ch)){clean_str ;// 统一替换成 空格}else{clean_strtolower(ch);// 是字母 → 强制转小写}}通用处理所有标点不只是句号逗号、感叹号、括号等全部变空格杜绝单词粘连比如 hello,world → 变成 hello world不会误判为一个单词统一大小写所有字母转小写实现不区分大小写统计为分割铺路把所有干扰字符都变成空格stringstream 可以完美分割自动忽略多个连续空格自动忽略开头 / 结尾的空格直接拿到纯单词不用手动写分割逻辑结语
map 与 unordered_map 结构实战指南：从随机链表复制到单词识别，再探稳定与非稳定排序
目录前言一、map结构的实际应用1.1 随机链表的复制1.2 前K个高频单词1.2.1 稳定排序与非稳定排序1.3 单词识别结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、map结构的实际应用1.1 随机链表的复制该题目在数据结构专栏的文章有过提及不过当时是用C写的随机链表的赋值随机链表的复制/* // Definition for a Node. class Node { public: int val; Node* next; Node* random; Node(int _val) { val _val; next NULL; random NULL; } }; */classSolution{public:Node*copyRandomList(Node*head){if(headnullptr)returnnullptr;mapNode*,Node*nodeMap;Node*copyheadnullptr;Node*copytailnullptr;Node*curhead;//创建新链表结构while(cur){Node*copynewNode(cur-val);if(copytailnullptr){//第一个结点初始化头尾copyheadcopytailcopy;}else{//新节点在尾部copytail-nextcopy;copytailcopy;}//记录原结点 - 新结点的映射nodeMap.insert({cur,copy});curcur-next;}//复制random指针curhead;Node*copycopyhead;while(cur){if(cur-randomnullptr){copy-randomnullptr;}else{//通过map查找原结点random对应的新结点copy-randomnodeMap[cur-random];}curcur-next;copycopy-next;}returncopyhead;}};解法核心思路红黑树std::map实现键值映射用std::map建立「原节点 → 新节点」的一一映射解决random指针无法直接复制的问题分两步遍历第一次遍历创建所有新节点构建新链表的next结构同时用map记录原节点和新节点的对应关系第二次遍历通过map的键值查找把原节点的random指针映射到新节点的random指针。核心逻辑map的有序性对本题无意义但它的 “键唯一 可查找” 特性刚好满足 “原节点→新节点” 的映射需求。要点补充map.insert({cur, copy})的作用把 “原节点cur” 作为键“对应的新节点copy” 作为值存入map。这一步是为了后续能通过 “原节点的指针” 快速找到 “对应的新节点”。nodeMap[cur-random]的本质这是std::map的查找操作底层是红黑树的遍历时间复杂度为O(logn)。比如原节点cur的random指向节点A通过nodeMap[A]就能找到新链表中对应的节点A’从而给新节点的random赋值。时间复杂度O(nlogn)两次遍历链表O(n)每次map的插入 / 查找操作O(logn)红黑树的高度总复杂度n×O(logn)O(nlogn)。空间复杂度O(n)map存储了n个 “原节点→新节点” 的映射占用O(n)空间新链表本身占用O(n)空间题目要求深拷贝这部分空间不计入 “额外空间”。在绝大多数场景下会用 “哈希表” 代指 “键值映射结构”不会严格区分底层是红黑树还是哈希表。以后看到有人明明用了红黑树的底层却也说是哈希表也不会困惑了1.2 前K个高频单词前K个高频单词要点补充注意这里map统计次数之后虽然map本身就是排好序的但是内部是对string不是对次数排序但是若要再使用mapint, string sortMap也是不对的map 的 key 必须唯一不允许重复。当多个单词出现相同频率时比如示例 1 中 “i” 和 “love” 频率都是 2先插入 {2, “i”}此时 sortMap 中 key2 存在。再插入 {2, “love”}因为 key2 已存在会直接覆盖之前的 “i”导致数据丢失。最终 sortMap 只会保留最后一个插入的同频率单词无法得到完整的结果。mapint, string sortMap不能使用但是multimapint, string sortMap是可以的。multimapint, string允许同一个 Key频率对应多个 Value单词所有同频率单词都能完整存储不会丢失数据。但是这样也是不建议的map和set顺便排序是可以的但是真的比起来在大量数据的情况下二者的效率是不如vector sort的如上图这种看似正确的写法最终也是错误的 排序逻辑完全不符合题目要求根本原因pairstring, int的比较优先级错误直接用greater会调用pairstring, int()比较大小pairstring, int 的默认比较规则是先比较第一个元素字符串字典序字典序小的排前面只有当第一个元素相等时才会比较第二个元素int数值。而用 greaterpairstring, int 会把这个逻辑反过来先按字符串字典序降序排序再按 int 数值降序 排序。这和题目要求的排序规则完全相反题目要求先按频率int降序频率相同再按字符串字典序升序具体例子验证以示例 1 为例输入words [i, love, leetcode, i, love, coding]countMapmapstring, int天然按字符串字典序升序存储{coding:1, i:2, leetcode:1, love:2}构造vectorpairstring, int v后顺序和 countMap 一致[{coding,1}, {i,2}, {leetcode,1}, {love,2}]执行sort(v.begin(), v.end(), greaterpairstring, int)后按字符串字典序降序排列结果变为[{love,2}, {leetcode,1}, {i,2}, {coding,1}]取前 k2 个单词[love, leetcode]但正确结果应该是[i, love]完全不符合要求。基于这样的原因这里就要自己实现一个仿函数来控制比较的逻辑可以看到依旧是没有通过全部测试用例的但是这次是111个测试用例中通过了31个第32个没有通过而且可以看到没过的用例是某两个词的顺序和正确的结果交换了原因是没有处理不同的单词有相同出现频率 按字典顺序排序这种情况这里也是可以通过打印验证的LeetCode有一个好处就是其打印的东西是可以看见的把需要打印的代码写上提交一下就可以了这里是有多种解决方案的1.2.1 稳定排序与非稳定排序首先补充一下几个概念一、什么是「稳定排序」稳定排序如果两个元素的比较键值相等排序后它们的相对位置和排序前保持一致。非稳定排序即使两个元素的比较键值相等排序后它们的相对位置可能被打乱。std::sort 是非稳定排序核心原因和它的实现原理直接相关。二、为什么 std::sort 不稳定1. 底层实现快速排序非稳定为核心C 标准库中std::sort 通常采用 Introsort内省排序主体是快速排序QuickSort快速排序的「分区partition」过程会通过交换元素实现这个交换是「无序」的 —— 即使两个元素的比较键值相等也可能被交换位置打乱原始相对顺序。只有当递归深度过深时会退化为堆排序HeapSort堆排序同样是非稳定排序。仅在数据量极小时会用插入排序稳定但整体仍属于非稳定排序。直观例子假设有一个待排序的数组元素是 (单词, 频率)structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second;}};// 排序前同频率2的 i 在 love 前面vectorpairstring,intv{{i,2},{love,2},{coding,1}};// 仅按频率排序忽略字典序用 sort 排序sort(v.begin(),v.end(),kv_pair())// 非稳定排序的结果可能变成{love,2}, {i,2}, {coding,1}// love 和 i 频率相同但相对位置被打乱了所以此时就有了第一种解决方案算法库中的stable_sort 是稳定排序按「频率降序」排序时同频率元素的相对位置会被保留即保留字典序。前面mapstring, int countMap是有序容器遍历顺序天然是「字符串字典序升序」→ 同频率的单词在 countMap 中已经按字典序排好了。用vectorpairstring, int v(countMap.begin(), countMap.end())构造后vector 里的元素顺序和 countMap 完全一致同频单词保持字典序。此时使用std::stable_sort会保证同频率的 “i” 仍在 “love” 前面。classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second;}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}//mapint, string sortMap;//multimapint, string sortMap;//迭代器区间构造vectorpairstring,intv(countMap.begin(),countMap.end());//默认是升序这里排降序,sort是个函数模板要传对象//sort(v.begin(), v.end(), kv_pair());//稳定的排序stable_sort(v.begin(),v.end(),kv_pair());for(auto[k,v]:v){coutk:vendl;}coutendl;vectorstringret;for(size_t i0;ik;i){ret.push_back(v[i].first);}returnret;}};说一下stable_sort(v.begin(), v.end(), kv_pair());中kv_pair()的底层调用步骤 1创建 kv_pair 临时对象kv_pair() 是结构体的无参构造函数调用会在栈上创建一个 kv_pair 类型的临时对象匿名对象。这个对象没有成员变量仅承载 operator() 这个重载方法。它的生命周期从传入 stable_sort 开始到 stable_sort 执行结束后销毁。步骤 2stable_sort 接收并使用这个函数对象stable_sort 是函数模板其核心签名可简化理解为templateclassRandomIt,classComparevoidstable_sort(RandomIt first,RandomIt last,Compare comp);这里的 Compare 就是 kv_pair 类型comp 是传入的 kv_pair() 临时对象。步骤 3stable_sort 内部调用 comp.operator() 比较元素stable_sort 底层基于归并排序实现排序过程中会不断调用 comp 对象的 operator() 方法完成元素比较每次需要比较两个元素 akv1和 bkv2时会执行comp.operator()(a,b);// 等价于 kv_pair()(a, b)operator() 逻辑是return kv1.second kv2.second;即如果 a 的频率 b 的频率返回 true → a 应该排在 b 前面否则返回 false → b 应该排在 a 前面若频率相等返回 false → stable_sort 会保留原始相对位置这是稳定排序的核心。步骤 4临时对象销毁stable_sort 执行完成后传入的 kv_pair() 临时对象会被自动析构栈上对象出作用域销毁。为什么要传 kv_pair() 而不是 kv_pairkv_pair 是类型名kv_pair() 是创建该类型的临时对象stable_sort 需要的是「可调用的对象」而非类型本身 —— 必须通过 () 构造对象才能让 stable_sort 调用其 operator()。Compare comp 是函数参数而非模板参数作用是接收一个具体的可调用对象需要用这个对象的 operator() 做比较。因此必须传 kv_pair()创建 kv_pair 类型的临时对象而非仅传类型名 kv_pair类型名无法被函数调用方案缺陷强依赖「countMap 是有序容器」的隐含特性如果后续不小心把mapstring, int改成unordered_mapstring, int无序哈希表更高效countMap 的遍历顺序会完全随机此时 stable_sort 保留的「相对位置」也会随机结果直接错误。代码可读性差其他开发者甚至未来的你看代码时会疑惑题目要求「同频按字典序升序」但比较函数里完全没提字典序为什么结果是对的必须追溯到 countMap 的类型、vector 的构造方式、stable_sort 的稳定性才能理解逻辑增加了理解成本。性能略差stable_sort 底层是归并排序时间复杂度虽然也是 O (n log n)但常数更大需要额外空间存储临时数据而 sort 是内省排序快速排序 堆排序效率更高刷题 / 工程中优先选 sort。基于这些缺陷就有了第二种方案由于稳定性是改不了的所以只能改变比较逻辑直接在比较函数中明确写出「频率降序 同频字典序升序」不依赖任何隐含特性代码更健壮、易读classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second||(kv1.secondkv2.secondkv1.firstkv2.first);}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}//mapint, string sortMap;//multimapint, string sortMap;//迭代器区间构造vectorpairstring,intv(countMap.begin(),countMap.end());//默认是升序这里排降序,sort是个函数模板要传对象sort(v.begin(),v.end(),kv_pair());//稳定的排序//stable_sort(v.begin(), v.end(), kv_pair());for(auto[k,v]:v){coutk:vendl;}coutendl;vectorstringret;for(size_t i0;ik;i){ret.push_back(v[i].first);}returnret;}};由于这里数据量不大找最大的前k个还可以考虑用大堆第三套方案classSolution{public:structkv_pair{booloperator()(constpairstring,intkv1,constpairstring,intkv2){returnkv1.secondkv2.second||(kv1.secondkv2.secondkv1.firstkv2.first);}};vectorstringtopKFrequent(vectorstringwords,intk){mapstring,intcountMap;for(autostr:words){countMap[str];}priority_queuepairstring,int,vectorpairstring,int,kv_pairpq(countMap.begin(),countMap.end());// //打印// for(auto [k,v] : v)// {// cout k : v endl;// }// cout endl;vectorstringret;for(size_t i0;ik;i){ret.push_back(pq.top().first);pq.pop();}returnret;}};这是优先队列大顶堆解法核心是用堆来维护「频率最高 同频字典序最小」的单词顺序直接取前 k 个即可。要点补充priority_queue 在 C 中默认是大顶堆但它的比较器是「小于」逻辑和 sort 相反所以我觉得这个很坑提供方法但是不建议用当 comp(a, b) 返回 true 时a 的优先级比 b 低会被放在 b 的下方。kv1.second kv2.second若 kv1 频率 kv2 频率 → 返回 true → kv1 优先级更低kv2 会被放到堆上方保证频率高的在前。kv1.second kv2.second kv1.first kv2.first若频率相同且 kv1 字典序 kv2 字典序 → 返回 true → kv1 优先级更低kv2 会被放到堆上方保证同频字典序小的在前。priority_queuepairstring, int, vectorpairstring, int, kv_pair pq(countMap.begin(), countMap.end());这里可以直接传kv_pair而不是kv_pair()的原因是priority_queue 的第三个参数是模板参数指定类型而 stable_sort 的第三个参数是函数参数传递对象C 中 priority_queue 的完整模板声明如下templateclassT,classContainervectorT,classComparelessTclasspriority_queue;T队列中存储的元素类型pairstring, intContainer底层存储容器的类型vectorpairstring, intCompare比较器的类型不是比较器对象是kv_pair 这个结构体类型。模板参数的作用是告诉编译器 “用什么类型”而非 “传递一个具体的对象”。因此需要传 kv_pair类型名而非 kv_pair()创建该类型的对象。你可能会问既然只指定了比较器类型 kv_pair那实际做比较的对象从哪来答案是priority_queue 会在构造时自动创建比较器对象当调用priority_queue...,kv_pairpq(countMap.begin(),countMap.end());priority_queue 的构造函数会先默认构造一个 kv_pair 类型的比较器对象调用 kv_pair 的无参构造函数因为 kv_pair 没有自定义构造函数编译器会生成默认的用这个默认创建的比较器对象来调整堆的顺序和 stable_sort 中手动传 kv_pair() 效果完全一致。只有当你的比较器有非默认构造函数比如需要传参数初始化时才需要在构造 priority_queue 时手动传对象。例如// 假设比较器需要一个阈值有带参构造函数structkv_pair{intthreshold;kv_pair(intt):threshold(t){}// 带参构造booloperator()(constautoa,constautob){...}};// 此时需要先创建带参数的比较器对象再传给构造函数kv_paircomp(10);// 创建带参数的对象priority_queue...,kv_pairpq(comp,countMap.begin(),countMap.end());而这里的 kv_pair 是无状态的没有成员变量仅重载了 operator()因此用默认构造的对象即可无需手动传。1.3 单词识别BITKY120 单词识别解题思路读入整行用 getline 读取带空格的完整句子清洗字符遍历每个字符非字母转空格字母统一转小写用 isalpha、tolower统计次数用 stringstream 按空格拆分单词unordered_map 统计每个小写单词出现次数自定义排序把哈希表转为 vector按次数从多到少次数相同按单词字典序从小到大排序格式输出按 单词:次数 逐行打印#includeiostream#includeunordered_map#includevector#includestring#includealgorithm#includesstreamusingnamespacestd;boolcompare(constpairstring,inta,constpairstring,intb){if(a.second!b.second)returna.secondb.second;returna.firstb.first;}intmain(){//1.安全读取整行输入包含空格如果输入为空直接退出程序string s;if(!getline(cin,s))return0;//清洗字符串string cleans;for(autoch:s){//如果不是字母(句号、逗号、空格、感叹号等),统一替换为空格if(!isalpha(ch))cleans ;//是字母强制转小写elsecleanstolower(ch);}//2.裁剪字符串并读入频率unordered_mapstring,intcount;stringstreamss(cleans);string word;//自动按空格分割无视连续空格/首尾空格直接读取纯单词while(ssword)count[word];//3.换容器 自定义排序vectorpairstring,intword_list(count.begin(),count.end());sort(word_list.begin(),word_list.end(),compare);//4.格式化输出for(autoe:word_list)coute.first:e.secondendl;return0;}说一下这道题目的细节点getline(cin, s)读取一整行文字cin s 遇到空格就停止读不完句子if (!getline)处理空输入边界防止程序崩溃这段代码的【核心灵魂】string clean_str;for(charch:s){// 遍历输入的每一个字符// 关键逻辑如果不是字母句号、逗号、空格、感叹号等if(!isalpha(ch)){clean_str ;// 统一替换成 空格}else{clean_strtolower(ch);// 是字母 → 强制转小写}}通用处理所有标点不只是句号逗号、感叹号、括号等全部变空格杜绝单词粘连比如 hello,world → 变成 hello world不会误判为一个单词统一大小写所有字母转小写实现不区分大小写统计为分割铺路把所有干扰字符都变成空格stringstream 可以完美分割自动忽略多个连续空格自动忽略开头 / 结尾的空格直接拿到纯单词不用手动写分割逻辑结语
