set、multiset、map、multimap在OJ的使用

目录

 练习1：随机链表的复制

1.思路1：通过插入拆分结点实现带随机指针链表的深拷贝

1.1.思路分析

1.2.代码实现

2.思路2：用 map 建立原链表与拷贝链表映射完成带随机指针链表的深拷贝

2.1.思路描述 

2.2.代码实现  - operator[](功能：插入 + 修改 或 查找)应用场景

练习 2:前 K 个高频单词 - 基于单词出现次数统计的 Top - K 问题

一、题目分析及相关理论基础

1.分析

2.排序算法稳定性

2.1.稳定性的定义

2.2.常见排序算法的稳定性说明

3.set、multiset、map、multimap 仿函数及比较规则解析

4.C++ 常见容器对应不同类型迭代器：

5.std::sort 和 std::stable_sort 不能用于 set、multiset、map、multimap 排序的原因

6.注意事项

二、两种解决思路 

1、思路一：使用map统计次数，结合vector与sort/stable_sort排序 

1.1.问题及解决方法

1.2.代码实现

(1)stable_sort排序

(2)sort排序

2、思路二：使用multise 或 set容器自身排序特性代替排序算法进行排序

2.1.问题及解决方法

2.2.代码实现

(1)multiset

(2)set

3、思路三：使用map统计次数，结合优先级队列（堆）解决 Top-K 问题

3.1. 问题及解决方法

3.2.代码实现 

4.总结

(2)仿函数使用差异

练习3：两个数组的交集

一、分析 

1.交集、差集应用场景

2.交集思路分析 - 时间复杂度O (N)

3.差集思路分析- 时间复杂度O (N)

4.并集思路分析 - 时间复杂度O(N)

二、代码实现

1.排序 + 去重的两种方式

2.交集代码

3.差集代码

4.并集代码

三、C++ 标准库提供交集、差集、并集算法

1.交集算法 std::set_intersection

2. 差集算法 std::set_difference

3.并集算法 std::set_union

 练习1：随机链表的复制

138. 随机链表的复制 - 力扣（LeetCode）

​​

1.思路1：通过插入拆分结点实现带随机指针链表的深拷贝

1.1.思路分析

(1)对一个带有随机指针（random 指针）的链表进行复制最重要是要解决以下两个核心问题：

• 问题1：深拷贝问题：普通链表的复制相对简单，只需依次复制每个节点的值和指针即可。但对于带有随机指针的链表，不能仅仅复制节点的值和指针指向，因为如果只是简单地复制指针，新链表和原链表会共享相同的节点，这是浅拷贝，不符合要求。需要实现深拷贝，即创建一个全新的链表，新链表中的每个节点都在内存中有独立的空间，与原链表的节点完全隔离，这样修改新链表的节点不会影响原链表，反之亦然。为了解决深拷贝问题，通常需要为原链表的每个节点创建一个对应的新节点，并正确设置新节点之间的 next 指针和 random 指针，确保新链表是原链表的完全独立副本。

• 问题2：正确处理随机指针的指向：在普通链表中，节点之间的连接关系是通过 next 指针顺序连接的，复制时按顺序复制即可。然而，带有随机指针的链表中，random 指针可以指向链表中的任意节点（包括自身），这使得复制过程变得复杂。在复制过程中，必须准确地确定每个新节点的 random 指针应该指向哪个新节点，以保证新链表中节点之间的随机连接关系与原链表一致。这就需要在复制过程中建立原链表节点和新链表节点之间的映射关系，以便根据原节点的 random 指针指向的原节点，找到对应的新节点并设置新节点的 random 指针。:

综上所述，对带有随机指针的链表进行复制时，深拷贝的实现和随机指针指向的正确处理是确保复制后的链表与原链表在结构和数据上完全一致的关键，也是需要重点解决的问题。

(2)思路描述

结点的插入是为了解决深拷贝问题，具体而言，通过将拷贝结点插入到原结点对应位置的后面，能够建立起拷贝结点和原结点之间紧密的关联关系（即建立映射关系）。这种映射关系的建立是后续操作的基础，因为它使得原链表与拷贝链表的结点一一对应，从而实现深拷贝，保证新链表与原链表在内存上相互独立。

在建立起上述映射关系后，原链表中每个结点的random指针指向的结点与拷贝链表中对应结点的random指针指向的结点也存在着对应关系。因此，当找到原结点的random指针指向的结点后，通过这种映射关系，就能迅速定位到拷贝链表中对应的拷贝结点，进而正确设置拷贝结点的random指针，确保拷贝链表的随机指针指向与原链表一致。

完成拷贝结点的random指针设置后，最后一步是将拷贝结点从原链表中拆分出来。在拆分过程中，需要恢复原链表的结构，并将拷贝结点重新组合，形成独立的拷贝链表。通过这种方式，既保留了原链表的完整性，又得到了一个与原链表在结构和数据上完全相同的拷贝链表，从而顺利完成对原链表的深拷贝操作。

总结：对带有随机指针的链表进行复制，核心在于通过三个关键步骤解决深拷贝问题。首先，将拷贝结点插入原结点之后，建立原结点与拷贝结点的映射关系，确保新链表与原链表在内存上相互独立；其次，基于该映射关系，准确设置拷贝结点的random指针，保证拷贝链表与原链表的随机指针指向一致；最后，拆分原链表与拷贝结点，恢复原链表结构并重新组合拷贝结点，生成独立的拷贝链表，最终实现对原链表完整且独立的深拷贝 。

1.2.代码实现

实现了一个复制带有随机指针的链表的功能，其核心思路是通过三个步骤来完成链表的复制，具体如下：

• 插入拷贝结点：遍历原链表，对于每个原结点，创建一个新的拷贝结点，并将其插入到原结点的后面。这样做的目的是让拷贝结点与原结点一一对应且相邻，方便后续设置随机指针和拆分链表。在这个过程中，使用临时指针next保存原结点的下一个结点，避免链表结构被破坏，然后将原结点的next指向拷贝结点，拷贝结点的next指向原结点原来的下一个结点。
• ​​
• 设置拷贝结点的随机指针：再次遍历原链表，由于在第一步中拷贝结点紧跟在原结点之后，因此可以通过原结点的随机指针来确定拷贝结点的随机指针指向。如果原结点的随机指针为空，那么对应的拷贝结点的随机指针也设为空；否则，拷贝结点的随机指针指向原结点随机指针所指向结点的下一个结点（即原结点随机指针指向的结点的拷贝结点）。
• ​​
• 拆分原链表和拷贝链表：第三次遍历原链表，将原链表和拷贝链表分离。在遍历过程中，恢复原链表中每个结点的next指针指向（即指向原来的下一个结点），同时构建拷贝链表。通过判断拷贝链表的尾指针copytail是否为空来确定是否需要初始化拷贝链表的头指针和尾指针，若为空则将当前拷贝结点设为头结点和尾结点，否则将当前拷贝结点连接到拷贝链表的尾部并更新尾指针。最后，将拷贝链表的尾结点的next指针设为空，完成拷贝链表的构建，并返回拷贝链表的头指针copyhead。
• ​​

class Solution 
{
public:Node* copyRandomList(Node* head) {//第一步：在原链表每个结点后插入其拷贝结点//目的是为后续拷贝random指针以及拆分链表做准备Node* cur = head;while (cur) {//暂存当前结点的下一个结点，以便后续恢复原链表结构Node* next = cur->next;//使用new分配内存创建新结点，值为当前原结点的值Node* copy = new Node(cur->val);//将当前原结点的next指针指向新创建的拷贝结点cur->next = copy;//将拷贝结点的next指针指向原结点原来的下一个结点copy->next = next;//移动到原链表的下一个结点cur = next;}//第二步：设置拷贝结点的random指针//依据原链表结点的random指针指向，设置拷贝链表中对应结点的random指针cur = head;while (cur) {//获取当前原结点对应的拷贝结点Node* copy = cur->next;if (cur->random == nullptr) {//若原结点的random指针为空，拷贝结点的random指针也设为空copy->random = nullptr;}else {//原结点的random指针指向的结点的下一个结点就是拷贝链表中对应的随机结点copy->random = cur->random->next;}//移动到原链表的下一个结点（跳过拷贝结点）cur = cur->next->next;}//第三步：拆分原链表和拷贝链表//将插入在原链表中的拷贝结点分离出来，形成独立的拷贝链表cur = head;Node* copyhead = nullptr;Node* copytail = nullptr;while (cur) {//获取当前原结点对应的拷贝结点Node* copy = cur->next;//暂存拷贝结点的下一个结点（即原链表中cur结点的下一个结点）Node* next = copy->next;//恢复原链表中cur结点的next指针指向cur->next = next;if (copytail == nullptr) {//若拷贝链表还未初始化，将当前拷贝结点设为头结点和尾结点copyhead = copytail = copy;}else {//将当前拷贝结点连接到拷贝链表的尾部copytail->next = copy;//更新拷贝链表的尾结点copytail = copytail->next;}//移动到原链表的下一个结点cur = next;}if (copytail) {//将拷贝链表的尾结点的next指针设为空，结束拷贝链表copytail->next = nullptr;}return copyhead;}
};

2.思路2：用 map 建立原链表与拷贝链表映射完成带随机指针链表的深拷贝

2.1.思路描述 

​​

对带有随机指针的链表进行深拷贝时，因随机指针指向不固定，要保证新链表和原链表在内存上相互独立且结构一致，关键在于解决原结点和拷贝结点的关联问题。采用 std::map 建立原链表结点和拷贝链表结点的映射关系，以此实现正确的深拷贝，具体步骤如下：

• 构建映射关系：使用 std::map 存储原链表结点指针和对应拷贝结点指针的键值对，建立两者的映射。
• 创建拷贝链表：遍历原链表，为每个原结点创建拷贝结点，将其值设为原结点的值，同时使用 map 的 operator[] 把原结点指针和拷贝结点指针存入 map，并将拷贝结点连接成拷贝链表。
• 设置随机指针：再次同时遍历原链表和拷贝链表，根据原结点 random 指针的指向情况，结合 map 中的映射关系，设置拷贝结点的 random 指针。
• 返回结果：完成拷贝链表构建和随机指针设置后，返回拷贝链表的头结点。

2.2.代码实现  - operator[](功能：插入 + 修改 或 查找)应用场景

代码思路：借助 std::map 建立原链表和拷贝链表结点的映射关系。先遍历原链表创建拷贝链表并建立映射，再遍历两个链表，依据映射设置拷贝结点的随机指针，最后返回拷贝链表头结点，实现带有随机指针链表的深拷贝。 

class Solution
{
public://该函数用于对带有随机指针的链表进行深拷贝Node* copyRandomList(Node* head){//使用std::map来建立原链表结点和拷贝链表结点之间的映射关系，//其中原链表结点指针作为键（key），拷贝链表结点指针作为值（value）-使用map建立KV模型std::map<Node*, Node*> copyNodeMap;//cur指针用于遍历原链表Node* cur = head;//copyhead指向拷贝链表的头结点，copytail指向拷贝链表的尾结点Node* copyhead = nullptr, * copytail = nullptr;//第一步：遍历原链表，创建拷贝链表并建立映射关系//从头开始遍历原链表，为每个原结点创建对应的拷贝结点，并将其连接成拷贝链表while (cur){//创建一个新的拷贝结点，其值与当前原结点的值相同Node* copy = new Node(cur->val);//使用map::operator[]的插入+修改功能，将原链表结点指针作为key，拷贝结点指针作为value存入map中//如果该key不存在，则插入新的键值对；如果已存在，则更新对应的value。copyNodeMap[cur] = copy;//使用map::operator[]的插入+修改让原链表和拷贝链表对应结点建立关联关系(即映射关系)。//处理拷贝链表的头结点和尾结点if (copytail == nullptr){//若拷贝链表的尾指针为空，说明拷贝链表还未初始化，//将当前拷贝结点设置为拷贝链表的头结点和尾结点copytail = copyhead = copy;}else{//若拷贝链表的尾指针不为空，将当前拷贝结点连接到拷贝链表的尾部，//并更新尾指针指向新的尾结点copytail->next = copy;copytail = copytail->next;}//移动到原链表的下一个结点cur = cur->next;}//重置cur指针，使其重新指向原链表的头结点//同时，copy指针指向拷贝链表的头结点cur = head;Node* copy = copyhead;//第二步：遍历原链表和拷贝链表，设置拷贝链表结点的random指针//再次从头开始遍历原链表和拷贝链表，根据原链表结点的random指针设置拷贝链表结点的random指针while (cur){//处理原结点的random指针为空的情况if (cur->random == nullptr){//若原结点的random指针为空，将对应的拷贝结点的random指针也设为空copy->random = nullptr;}else{// 当cur指针指向的当前原结点存在有效的random指针（即cur->random不为空）时：// 1. 由于此前已通过std::map建立了原链表结点与拷贝链表结点的映射关系（KV模型），//    其中原结点指针作为key，对应的拷贝结点指针作为value。// 2. 利用map的operator[]成员函数的查找功能，将当前原结点random指针指向的原结点（即cur->random）作为key传入。//    此时，map会根据key在内部存储的键值对中进行查找，返回与该key对应的value，即该原结点对应的拷贝结点指针。// 3. 将查找到的拷贝结点指针赋值给copy指针指向的当前拷贝结点的random指针，//    从而使得当前拷贝结点的random指针正确指向与原链表中相对应的随机结点，//    确保拷贝链表的random指针连接关系与原链表一致。copy->random = copyNodeMap[cur->random]; // copyNodeMap[cur->random] 通过key（原结点指针）获取对应的拷贝结点指针（value）// 注：此处使用map::operator[]的查找功能，以当前原结点random指针指向的原结点作为key，精准获取对应的拷贝结点指针//总结：当原结点的random指针不为空时，由于之前已经建立了原结点和拷贝结点的映射关系，利用map的operator[]查找功能，//以当前原结点的random指针指向的原结点作为key，在map中查找对应的拷贝结点指针,然后将该拷贝结点指针赋值给当前拷贝结点的random指针，//确保拷贝链表的random指针连接关系与原链表一致。}//原链表和拷贝链表的当前结点指针都向后移动一位，继续遍历cur = cur->next;copy = copy->next;}//第三步：返回拷贝链表的头结点//完成拷贝链表的创建和random指针的设置后，返回拷贝链表的头结点return copyhead;}
};

练习 2:前 K 个高频单词 - 基于单词出现次数统计的 Top - K 问题

692. 前K个高频单词 - 力扣（LeetCode）

​

一、题目分析及相关理论基础

1.分析

本题属于经典的 Top - K 问题，解决此类问题通常涉及到数据的排序与筛选策略。核心任务是找出前 K 个高频单词，并按照单词出现频率从高到低排序，当频率相同时则依据字典序排序。其考点聚焦于两个关键层面：其一，对排序稳定性的考量，这要求必须选用具有稳定性的排序算法，从而保证相同频率单词在排序前后的相对顺序不发生改变；其二，灵活运用仿函数来精准控制比较规则，通过重载函数调用运算符，定制先比较频率，在频率相同的情况下再比较字典序的逻辑，以此实现符合题目严格要求的排序结果。

2.排序算法稳定性

​

2.1.稳定性的定义

排序算法的稳定性指在排序过程中，相等元素的相对顺序在排序前后保持不变。若原序列中元素 A 和元素 B 相等，且 A 在 B 之前，经排序后 A 仍在 B 之前，该算法就是稳定的；反之则不稳定。

2.2.常见排序算法的稳定性说明

3.set、multiset、map、multimap 仿函数及比较规则解析

(1)基于存储元素值比较的关联式容器：set 和 multiset

• 仿函数：set 和 multiset 的模板参数中都有 class Compare = less<T> ，默认仿函数均为 less<T> 。仿函数是通过重载 operator() 来实现类似函数调用行为的对象，less<T> 按照小于关系对元素进行比较。
• 比较规则：二者均基于元素值确定存储顺序，遵循严格弱序规则。区别在于 set 不允许元素重复，而 multiset 允许。例如对于 set<int> 和 multiset<int> ，默认按 int 值从小到大排列；若想自定义为降序，可定义仿函数：

• struct greater 
  {bool operator()(const int& a, const int& b) const {return a > b;}
  };
  set<int, greater> s;
  multiset<int, greater> ms;

• 比较基准：set和multiset的比较与排序直接基于容器内存储的元素类型T，不涉及额外的键值或映射关系。

(2)基于键值比较的关联式容器：map 和 multimap

①仿函数机制：map与multimap模板参数均包含class Compare = less<Key>，默认采用less<Key>仿函数，专门用于比较键（Key类型）。该仿函数通过重载operator()实现，默认按严格弱序对键值进行升序比较。

②核心比较规则
二者均基于键值的比较结果对键值对进行排序，遵循严格弱序原则。区别在于：

• map：键具有唯一性，不允许重复键值；
• multimap：允许同一键存在多个键值对，适用于多值映射场景。
  
  例如，对于map<string, int>和multimap<string, int>，默认按键（string类型）的字典序升序排列。

③自定义规则实现
如需改变默认排序逻辑，可通过以下步骤定制：

• 定义新的仿函数类，重载operator()指定比较逻辑；
• 将自定义仿函数作为模板参数传入容器定义。

④map和multimap的比较基准是容器中键值对的键（Key 类型）

解析：在map和multimap这两种关联式容器中，元素以键值对的形式存储，即pair<const Key, T>。容器内部的比较和排序操作都是针对键（Key）进行的，与值（T）无关。默认情况下，使用less<Key>仿函数按照键的严格弱序对键值对进行升序排序。如果需要自定义比较规则，也是通过自定义仿函数来改变对键的比较方式，从而实现对容器内键值对比较与排序规则的定制。

4.C++ 常见容器对应不同类型迭代器：

• 随机访问迭代器（RandomAccessIterator，支持 ++、--、+、-）：可向前或向后移动任意个元素，能比较相对位置。对应容器有 vector（动态数组）、deque（双端队列）、array（固定大小数组）、string（字符串容器）。
• 双向迭代器（BidirectionalIterator，支持 ++、--）：能向前和向后逐个移动元素。list（双向链表）、set（元素唯一的关联容器）、multiset（允许元素重复的关联容器）、map（键唯一的键值对关联容器）、multimap（允许键重复的键值对关联容器）使用此类迭代器。
• 单向迭代器（ForwardIterator，支持 ++）：仅能向前逐个移动元素，forward_list（单向链表）使用该迭代器。
• 输入 / 输出迭代器：输入迭代器（InputIterator）用于从输入流读取元素，如 istream_iterator；输出迭代器（OutputIterator）用于向输出流写入元素，如 ostream_iterator。

5.std::sort 和 std::stable_sort 不能用于 set、multiset、map、multimap 排序的原因

• 迭代器类型限制：前者要求 RandomAccessIterator（随机访问迭代器），支持如 it + n 的跳跃式访问；而 set、multiset、map、multimap 的迭代器是 BidirectionalIterator（双向迭代器），只能逐个移动，无法满足排序需求。
• 容器特性：set 和 multiset 插入元素时会自动按规则排序，无需外部打乱再排序；map 和 multimap 以键值对存储，按键自动排序，外部排序会破坏其基于键有序的内部结构和数据组织方式。

6.注意事项

• map::operator[] 功能多样：当键不存在时插入新键值对，键存在时修改值，也可用于查找访问值，若键不存在则先插入并返回默认值。
• map 存储的元素是 pair<key, value> ，其迭代器指向 pair 类型，通过迭代器可访问每个键值对的键和值。 

二、两种解决思路 

题目分析：本题为 “前 K 个高频单词” 问题，给定单词列表words和整数k，需返回前k个出现次数最多的单词，按出现频率由高到低排序，频率相同则按字典序排序。本质考点涉及排序算法的稳定性，即相等元素在排序前后相对顺序保持不变。

1、思路一：使用map统计次数，结合vector与sort/stable_sort排序 

• 解析：利用map统计单词列表中各单词出现的次数，将map中的键值对（单词 - 出现次数）转移到vector中。随后，编写自定义仿函函数，依据单词出现频率和字典序制定比较规则，使用std::sort或std::stable_sort等排序算法对vector进行排序，从而得到前k个高频单词。其中std::sort平均时间复杂度较优但不保证稳定性；std::stable_sort具有稳定性，当单词频率相同时能维持其原有顺序。

1.1.问题及解决方法

(1)问题 1 - 迭代器类型不匹配：sort 函数底层要求接收随机迭代器，而 map 的底层迭代器是双向迭代器，这就导致无法直接使用 sort 函数对 map 进行排序。

解决方法：将 map 中存储的元素 pair<string, int> 插入到 vector 中。由于 vector 的迭代器是随机迭代器，且随机迭代器可以接收双向迭代器，所以可以直接使用 map<string, int> 的迭代器区间来构造 vector<pair<string

(2)问题 2 - 构造 vector 的方式优化：不建议使用 push_back 函数不断尾插 map 存储的元素 pair<string, int> 来构造 vector ，这种方式效率相对较低且代码不够简洁。

解决方法：直接利用 vector 迭代器可接收双向迭代器的特性，使用 map 的迭代器区间构造 vector ，这样可以更高效、简洁地完成数据从 map 到 vector 的转移。

(3)问题 3 - 排序规则自定义：使用 sort 函数对 vector 的存储元素 pair<string, int> 进行排序时，pair 支持比较大小，但其默认的 pair::operator< 比较规则是按 pair 的 first 或者在 first 相等时按 second 进行比较，而本题要求按照 pair.second （即单词出现的次数）进行排序。

解决方法：自定义仿函数来改变比较规则。通过重载 () 运算符，编写一个仿函数类，在其中定义按照 pair.second 进行比较的逻辑。例如：

• struct Compare
  {bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {return kv1.second > kv2.second;//按照单词次数进行排序}
  };

然后在调用 sort 函数时，将该仿函数对象作为参数传入，如 sort(v.begin(), v.end(), Compare()); 。

(4)问题 4 - 排序算法稳定性问题：sort 函数底层是快速排序算法，快速排序是不稳定的排序算法。这就意味着，在使用 map 统计次数后，虽然相同频率的单词在 map 中按字典序排好了序（如 “i” 在 “love” 前面），但使用 sort 函数对 pair<string, int> 按照单词次数进行排序时，不能保证这种相同频率单词的字典序稳定性，即排序后可能无法保证 “i” 仍在 “love” 前面。

解决方法：

方式 1：使用 std::stable_sort 函数来代替稳定性差的 sort 函数进行排序。std::stable_sort 是一个稳定的排序算法，它能保证相等元素在排序前后的相对顺序不变。使用方式与 sort 类似，如 stable_sort(v.begin(), v.end(), Compare()); 。使用比较规则如下：

• struct Compare
  {bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {return kv1.second > kv2.second;//按照单词次数进行排序}
  };

方式 2：进一步完善自定义仿函数。不仅要让仿函数控制 sort 的比较逻辑，使得次数大的元素排在前面（实现降序），还要在次数相等的情况下，让单词字典序小的排在前面（实现升序）。使用比较规则如下：

• struct Compare
  {bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const{return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);}
  };

需要注意的是，这种方式只是通过自定义仿函数控制比较规则，让 sort 函数在本题的排序中表现出一定的稳定性，但并不能从底层改变 sort 函数（快速排序）本身的不稳定性。 

1.2.代码实现

(1)stable_sort排序

(2)sort排序

2、思路二：使用multise 或 set容器自身排序特性代替排序算法进行排序

• 解析：先用map统计单词出现次数，之后不采用传统排序算法，而是利用set或multiset容器自身具备的排序功能。通过自定义仿函函数设定比较规则，使容器在插入元素时，自动按照单词频率从高到低、频率相同按字典序的方式进行排序，进而筛选出前k个高频单词 。set中元素具有唯一性，multiset允许元素重复，可根据实际情况选用。

2.1.问题及解决方法

(1)问题：在解决前 K 个高频单词问题时，使用multimap<int, string>替代sort函数进行排序会存在严重缺陷。multimap默认按单词出现次数（key）排序，当需满足 “出现次数相同则按字典序对单词（value）排序” 的要求时，自定义仿函数会面临困难。由于key仅为次数值，与单词（value）分离，需在仿函数中添加复杂逻辑，通过迭代器查找相同key关联的不同单词（value）再进行字典序比较，导致仿函数代码冗长、逻辑复杂，增加出错风险与维护难度。

• 解决方案：选用multiset<pair<string, int>>替代multimap<int, string>。multiset<pair<string, int>>中pair整合了单词和出现次数信息，自定义仿函数时可直接操作pair成员。先比较pair第二个成员（出现次数）实现按频率排序，次数相等时比较第一个成员（单词）实现字典序排序，代码逻辑简洁，易于理解与编写，有效解决multimap<int, string>存在的问题。

(2)multimap<int, string>使用greater<key>比较规则代码居然可以通过的原因分析

①分析上面代码能够通过的原因：

在提供的代码中，使用了multimap<int, string, greater<int>> sortMap; ，这里利用multimap的默认比较规则greater<int>来实现按单词出现次数从大到小排序。之所以能在当前平台巧合通过，是因为在当前平台下红黑树（multimap底层常用数据结构）对于相等key值（即相同单词出现次数）的插入策略刚好使得排序结果符合预期。

也就是说，在当前平台上，当有相同出现次数的单词插入multimap时，红黑树的插入操作恰好让这些单词按照某种顺序排列好了，可能是因为插入到特定子树等原因，使得后续遍历multimap获取前k个高频单词时得到了看似正确的结果。但这并非是代码逻辑严谨导致的必然正确结果，而是依赖于当前平台红黑树的特定实现。

②不使用multimap<int, string>替代sort函数进行排序的另一个问题

不同平台下，红黑树等数据结构对于相等值的插入规则存在差异。比如，在某些平台下，红黑树在插入相等key值时，可能将其插入到左子树，而在另外一些平台可能插入到右子树。

对于multimap<int, string, greater<int>> ，如果出现次数相同的单词插入顺序因为平台差异而改变，那么最终的排序结果就可能与预期不符。比如原本希望按照字典序排列相同频率的单词，但由于相等key值插入到不同子树，导致遍历顺序改变，得到的单词顺序就可能出错。更严重的情况下，还可能因为这种底层实现差异导致代码运行时报错，比如迭代器遍历顺序混乱等问题。所以不能单纯依赖multimap的默认规则来实现稳定可靠的排序，这就是不使用它替代sort函数进行排序的另一个重要原因。

(3)使用 multiset<pair<string, int>> 代替 std::sort 来进行排序。

multiset 也是一种关联式容器，它与 set 类似，但允许元素重复。将单词和其出现次数组成 pair<string, int> 作为 multiset 的元素，利用 multiset 的排序功能来实现题目要求的排序。

问题：multiset 默认使用 less<key> （这里 key 为 pair<string, int> ）作为比较规则，即按照 pair::operator< 的规则进行比较排序，而这不符合本题要求。

解决方法：同样需要自定义仿函数来控制比较规则。自定义仿函数的规则为：单词出现次数大的情况下，让次数大的排在前面（实现降序）；在次数相等的情况下，让单词字典序小的排在前面（实现升序）。由于 const 对象会调用 const 仿函数，则自定义的仿函数最好使用 const 修饰。例如：

• struct Compare
  {bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const{return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);}
  };multiset<pair<string, int>, Compare> sortSet;

(4)使用set<pair<string, int>> 可以代替std::sort 来进行排序的原因

set是一种关联式容器，其特性是不允许key冗余 ，即不允许重复元素存在。在本题情境下，set的key是pair<string, int> ，其中包含了单词和该单词对应的出现次数。由于每个单词及其出现次数的组合是独特的（不同单词出现次数可能相同，但单词与出现次数的组合是特定的 ），所以不会出现重复的key，满足set对元素唯一性的要求，能够有效存储题目相关数据。

2.2.代码实现

(1)multiset

class Solution 
{
public://自定义仿函数Compare，用于比较pair<string, int>//比较规则：首先比较出现次数（kv1.second和kv2.second），出现次数多的排在前面//如果出现次数相同，则比较单词的字典序（kv1.first和kv2.first），字典序小的排在前面struct Compare {bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const {return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);}};vector<string> topKFrequently(vector<string>& words, int k) {//用于统计每个单词出现的次数，key为单词，value为出现次数map<string, int> countMap;//遍历单词列表wordsfor (auto& str : words) {//对每个单词，在countMap中对应的值加1，统计其出现次数countMap[str]++;}//使用自定义的Compare仿函数，创建一个multiset，用于存储单词及其出现次数的pair，并自动排序//排序规则按照Compare仿函数定义的：先按出现次数降序，次数相同按字典序升序multiset<pair<string, int>, Compare> sortSet(countMap.begin(), countMap.end());//用于存储最终结果，即前k个高频单词vector<string> ret;//获取sortSet的起始迭代器auto it = sortSet.begin();//循环k次，将前k个高频单词加入结果向量ret中while (k--) {//将当前迭代器指向的pair中的单词（first成员）加入结果数组ret.push_back(it->first);//移动迭代器到下一个元素++it;}//返回前k个高频单词的结果数组return ret;}
};

(2)set

3、思路三：使用map统计次数，结合优先级队列（堆）解决 Top-K 问题

• 解析： 当数据量不大时，可采用 map 来统计单词出现的次数，其原理与思路 1 中统计次数部分相同。然后结合 priority_queue（优先级队列，底层通常是堆数据结构）来解决 Top - K 问题。priority_queue 会根据自定义的比较规则对元素进行自动排序，通过调整堆的大小和元素的进出，最终可以得到前 k 个高频单词。

3.1. 问题及解决方法

问题及解决：
与前面思路类似，priority_queue 也需要自定义仿函数来控制比较规则。因为默认的比较规则不符合本题要求，需要编写仿函数来实现按照单词出现频率从高到低排序，在频率相同的情况下按照字典序排序。例如：

struct Compare
{bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) const{return kv1.second > kv2.second || (kv1.second == kv2.second && kv1.first < kv2.first);}
};priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> pq;

在将统计好次数的单词 - 频率对插入 priority_queue 后，通过适当的操作（如控制元素的弹出次数等），可以获取前 k 个高频单词。

3.2.代码实现 

class Solution
{
public://自定义仿函数Compare，用于小堆的比较规则//当两个单词出现次数相同时，按照字典序比较（字典序小的在前）//当出现次数不同时，出现次数多的在前struct Compare{bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2){return kv1.second == kv2.second ? kv1.first < kv2.first : kv1.second > kv2.second;}};vector<string> topKFrequent(vector<string>& words, int k){//使用map来统计每个单词出现的次数，map会自动按照键（单词）的字典序排序//这里利用了map的特性，保证相同单词的统计正确，且天然具有一定的顺序性map<string, int> countMap;for (auto& str : words){countMap[str]++;}//创建一个小堆pq，存储单词及其出现次数的pair//小堆的比较规则由自定义的Compare仿函数控制//这样小堆中出现次数多的（或出现次数相同但字典序小的）会排在前面priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> pq;for (auto& it : countMap){//将统计好的单词及其出现次数的pair插入小堆pq.push(it);//如果小堆的大小超过了k，说明当前小堆中出现次数相对少的元素在堆顶//将其弹出，保证小堆中始终是前k个高频单词（或出现次数相同字典序小的）if (pq.size() > k){pq.pop();}}//创建一个大小为k的vector来存储最终结果//这里的vector用于存放前k个高频单词，提前指定大小为k可以避免在后续插入元素时发生不必要的内存重新分配和拷贝操作，提高效率vector<string> ret(k);for (int i = k - 1; i >= 0; i--){//从小堆中依次取出堆顶元素（即前k个高频单词），存入结果vector中//此时小堆pq中存放的是前k个高频单词及其出现次数的键值对（pair）//pq.top()获取堆顶的键值对，.first用于获取该键值对中的单词（string类型）//之所以从后往前（k - 1到0）存储到ret中，是因为小堆的特性是堆顶为最小元素（按我们设定的比较规则）//依次弹出堆顶元素，倒序存储可以使最终结果vector中的单词顺序符合从高频到低频（出现频率相同按字典序）的要求ret[i] = pq.top().first;//弹出已经处理过（存入ret）的堆顶元素，使得下一次pq.top()获取的是新的堆顶元素（下一个高频单词相关的键值对）pq.pop();}return ret;}
};

4.总结

(1)思路共性：上述三种思路（map 统计次数 + 仿函数控制 sort 排序、map 统计次数 + 优先级队列（堆）、不借助 sort 用 multiset 排序 ）均通过自定义仿函数来控制比较规则，实现升序或降序效果。

• 对于map和set系列容器（如multimap、multiset、set ），仿函数控制的是key（或元素整体，如pair<string, int> ）的比较规则。在这些容器中，仿函数用于改变其内部默认的排序逻辑，以满足题目中对单词按频率和字典序的特定排序要求。
• 对于排序算法sort，仿函数控制的是函数对象Compare的比较规则。在使用sort函数对容器（如vector ）中的元素进行排序时，通过传入自定义的仿函数对象，来指定元素之间的比较方式，从而实现符合题目要求的排序。

(2)仿函数使用差异

• 在使用方式上，sort函数需要传递仿函数对象 。例如在sort(v.begin(), v.end(), Compare()); 中，Compare() 就是一个仿函数对象，它明确地将仿函数实例化后传递给sort函数，以此来改变排序规则。
• 而对于multiset或set等容器，在定义容器时只需传递仿函数类型 。例如multiset<pair<string, int>, Compare> sortSet; ，这里将仿函数类型Compare作为模板参数传递给multiset，容器内部会根据这个仿函数类型来构建比较规则，不需要像sort函数那样显式地实例化仿函数对象进行传递。

练习3：两个数组的交集

349. 两个数组的交集 - 力扣（LeetCode）

注意事项：

• set 功能：实现排序和去重，可用于解决元素是否存在的问题（K 模型） 。
• multiset 功能：具备排序功能，但不会对重复元素进行去除（存在冗余元素） 。
• map 功能：用于通过键（key）查询值（value） （K 模型），也可借助operator[]++统计元素出现次数（KV 模型） 。

一、分析 

1.交集、差集应用场景

• 交集：在数据同步相关算法中广泛应用，比如网盘的同步功能。在本地数据目录和服务器数据目录的比对过程中，需要找出两边都存在的数据，这就涉及到求交集操作。只有确定了交集数据，才能进一步判断哪些数据在本地有但服务器没有（需上传），哪些数据在服务器有但本地没有（需下载） 。
• 差集：在数据同步场景中，除了关注交集数据，还需要确定哪些数据是两边不共有的，即差集数据。比如在本地删除了某些文件后，服务器需要通过与本地数据对比，找出本地已删除的数据并同步删除；或者本地新增了某些文件，服务器没有，需要确定这些新增文件以便上传同步 。

2.交集思路分析 - 时间复杂度O (N)

注：这里的 N 是指两个数字序列的元素总数之和。  

假设有两个已排序且去重的数字序列（一般先对输入数组进行排序和去重处理） ，使用两个迭代器分别指向这两个序列的起始位置。

• 当两个迭代器指向的元素相等时，说明找到了一个交集元素，将其添加到结果集中，然后两个迭代器都向后移动一位，继续寻找下一个交集元素。
• 当两个迭代器指向的元素不相等时，较小元素所在迭代器向后移动一位。原因在于，在升序去重的序列中，较小元素后面的元素只会更大，而另一个序列当前元素也比它大，所以另一个序列不可能存在与它相等的值，因此较小元素迭代器移动，而较大元素迭代器不移动，因为较小元素后面的元素有可能与较大元素构成交集。

3.差集思路分析- 时间复杂度O (N)

注：这里的 N 是指两个数字序列的元素总数之和。  

同样针对两个已排序的数字序列，使用两个迭代器分别指向两个序列起始位置。

• 当两个迭代器指向的元素相等时，说明这两个元素都不是差集元素，两个迭代器同时向后移动一位，继续比较后续元素。
• 当两个迭代器指向的元素不相等时，较小元素是差集元素。这是因为在升序去重序列中，较小元素后面的值只会更大，而另一个序列当前元素比它大，所以该较小元素不可能是交集元素，只能是差集元素。此时较小元素迭代器向后移动一位，较大元素迭代器不移动，因为较大元素可能与较小元素移动后的值相等或小于。当其中一个迭代器遍历到序列末尾时，停止比较，此时另一个未遍历完的序列中剩余元素也属于差集元素。

4.并集思路分析 - 时间复杂度O(N)

注：这里的 N 是指两个数字序列的元素总数之和。 

• 利用 set 容器的去重特性，将两个数字序列的所有元素依次插入到一个 set 中。由于 set 会自动去除重复元素，最终 set 中存储的所有元素就是这两个序列的并集 。

二、代码实现

1.排序 + 去重的两种方式

(1)方式 1：借助 C++ 标准库中的算法std::sort(排序)和std::unique(去重)。

std::sort是一个强大的排序算法，它要求传入的迭代器必须是双向迭代器，能够对容器内元素进行排序。std::unique是去重算法，它采用双指针实现，要求传入单向迭代器。如果数组存储在vector中，使用顺序为：先调用std::sort对vector中的元素进行排序，例如std::sort(nums1.begin(), nums1.end()); ；然后调用std::unique去重，std::unique(nums1.begin(), nums1.end()); 。需要注意的是，std::unique并不会真正删除重复元素，而是将重复元素移动到容器末尾，并返回去重后最后一个不重复元素的下一个位置迭代器，通常需要结合erase函数来真正删除多余元素 。

unique - C++ Reference (cplusplus.com)

(2)方式2:利用set容器的特性排序 + 去重。

set容器的构造函数可以接收迭代器区间作为参数，在构造过程中，会自动对传入的元素进行排序和去重。只要不同容器存储的数据类型一致，并且满足迭代器类型匹配要求（例如都是正向迭代器、双向迭代器等 ），就可以使用一个容器的迭代器区间去初始化另一个容器。例如set<int> s1(nums1.begin(), nums1.end()); ，这行代码会将nums1中的元素插入到set中，并完成排序和去重操作。

2.交集代码

2.1.思路 1：首先使用set对两个数组分别进行排序和去重。然后将其中一个set中的元素逐个插入到另一个set中，在插入过程中，利用set的特性（insert操作返回一个pair，其中second表示插入是否成功，若元素已存在则插入失败 ），插入失败的元素即为两个数组的交集元素，将其保存到结果容器中。

class Solution
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2){//使用nums1迭代器区间范围的元素初始化set s1，//set容器会自动对插入的元素进行排序和去重操作set<int> s1(nums1.begin(), nums1.end());//使用nums2的元素范围迭代器区间范围的元素初始化set s2，//set容器会自动对插入的元素进行排序和去重操作set<int> s2(nums2.begin(), nums2.end());//用于存储两个集合交集结果的整数数组vector<int> v;//遍历set s1中的每个元素，这里将元素命名为keyfor (int key : s1){//将key插入到set s2中，insert操作会返回一个pair//该pair的第一个元素是一个迭代器，指向插入的元素或已存在的相同元素//第二个元素是一个bool值，表示插入操作是否成功（true表示插入成功，false表示元素已存在）pair<set<int>::iterator, bool> ret = s2.insert(key);//如果插入操作失败（即元素已存在于s2中）if (!ret.second){//说明该元素是nums1和nums2的交集元素，将其添加到结果数组v中v.push_back(key);}}//返回计算得到的两个集合的交集结果向数组return v;}
};

复杂度分析：时间复杂度为 O (N*logN) ，这是因为set的插入操作平均时间复杂度为 O (logN) ，需要插入 N 个元素；空间复杂度为 O (N) ，主要是因为需要额外的set来存储数据。

2.2.思路2：对两个去重有序区间进行遍历，比较对应位置的元素。如果元素相等，则将其作为交集元素存入结果容器；如果不相等，则移动较小元素所在区间的迭代器，继续比较，直到其中一个区间遍历完毕。

class Solution 
{
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {//排序+去重的两种方式//方式1：使用算法库提供的sort排序 + unique去重//sort(nums1.begin(), nums1.end()); //对数组nums1进行排序//unique(nums1.begin(), nums1.end()); //对排序后的nums1进行去重// sort(nums2.begin(), nums2.end()); // 对数组nums2进行排序// unique(nums2.begin(), nums2.end()); // 对排序后的nums2进行去重//方法2：使用set自身的排序 + 去重功能//使用nums1的迭代器区间范围的元素初始化set s1，set会自动对元素进行排序和去重set<int> s1(nums1.begin(), nums1.end());// 使用nums2的迭代器区间范围的元素初始化set s2，set会自动对元素进行排序和去重set<int> s2(nums2.begin(), nums2.end());//定义迭代器it1指向s1的起始位置auto it1 = s1.begin();//定义迭代器it2指向s2的起始位置auto it2 = s2.begin();//用于存储交集结果的整数数组vector<int> v;//当两个迭代器都没有到达各自set的末尾时，进行循环比较//只要有一个迭代器遍历完对应set，就说明交集查找完毕while(it1 != s1.end() && it2 != s2.end()) {//如果it1指向的元素小于it2指向的元素if(*it1 < *it2){//it1向后移动一位，继续比较下一个元素++it1; }//如果it2指向的元素小于it1指向的元素else if(*it2 < *it1){//it2向后移动一位，继续比较下一个元素++it2; }//如果两个迭代器指向的元素相等else{//此时迭代器it1与it2遍历到相等元素，该元素就是交集元素//将其尾插到数组v中进行存放v.push_back(*it1); //it1向后移动一位，继续比较下一个元素++it1; //it2向后移动一位，继续比较下一个元素++it2; }}//返回计算得到的交集结果数组return v;}
};

复杂度分析：时间复杂度为 O (N) ，因为只需要对两个set进行一次遍历；空间复杂度为 O (N) ，用于存储去重后的set以及结果vector 。

3.差集代码

算法思路：对两个去重有序区间进行遍历，当两个迭代器指向的元素相等时，两个迭代器同时移动；当不相等时，较小元素所在迭代器移动，同时将较小元素作为差集元素存入结果容器，直到其中一个区间遍历完毕，然后将另一个区间剩余元素也添加到差集结果中。

class Solution
{
public:vector<int> difference(const vector<int>& nums1, const vector<int>& nums2){//使用set对nums1进行去重和排序，s1包含了nums1中的不重复元素且按升序排列set<int> s1(nums1.begin(), nums1.end());//使用set对nums2进行去重和排序，s2包含了nums2中的不重复元素且按升序排列set<int> s2(nums2.begin(), nums2.end());//用于存储差集结果的整数数组vector<int> v;//定义迭代器it1指向s1的起始位置auto it1 = s1.begin();//定义迭代器it2指向s2的起始位置auto it2 = s2.begin();//当两个迭代器都没有到达各自set的末尾时，进行循环比较while (it1 != s1.end() && it2 != s2.end()){//如果it1指向的元素小于it2指向的元素if (*it1 < *it2){//将it1指向的元素添加到差集结果数组v中v.push_back(*it1);//it1向后移动一位，继续比较++it1;}//如果it2指向的元素小于it1指向的元素else if (*it2 < *it1){//it2向后移动一位，继续比较++it2;}//如果两个迭代器指向的元素相等else{//两个迭代器都向后移动一位，继续比较下一对元素++it1;++it2;}}// 将s1中剩余未处理的元素添加到差集结果数组v中while (it1 != s1.end()){v.push_back(*it1);++it1;}//将s2中剩余未处理的元素添加到差集结果数组v中while (it2 != s2.end()){v.push_back(*it2);++it2;}//返回计算得到的差集结果数组vreturn v;}
};

4.并集代码

算法思路：利用 set 容器的去重特性，将两个数字序列的所有元素依次插入到一个 set 中。由于 set 会自动去除重复元素，最终 set 中存储的所有元素就是这两个序列的并集 。

class Solution
{
public://函数用于计算两个数组的并集vector<int> union(const vector<int>& nums1, const vector<int>& nums2) {set<int> s;//将第一个数组的元素插入到set中for (int num : nums1) {s.insert(num);}//将第二个数组的元素插入到set中for (int num : nums2) {s.insert(num);}//将set中的元素复制到vector中作为并集结果vector<int> v(s.begin(), s.end());return v;}
};

三、C++ 标准库提供交集、差集、并集算法

1.交集算法 std::set_intersection

set_intersection - C++ Reference (cplusplus.com)

std::set_intersection 算法用于计算两个有序区间的交集。它会找出两个有序区间中共同存在的元素，并将这些元素存储到指定的目标区间中。 

时间复杂度：该算法的时间复杂度也是 O(n+m)，其中 n 和 m 分别是两个输入区间的长度，因为同样需要遍历两个区间的元素来确定交集。

2. 差集算法 std::set_difference

set_difference - C++ Reference (cplusplus.com)

std::set_difference 算法用于计算两个有序区间的差集。它会找出在第一个有序区间中存在，但在第二个有序区间中不存在的元素，并将这些元素存储到指定的目标区间中。

时间复杂度：该算法的时间复杂度同样为 O(n+m)，其中 n 和 m 分别是两个输入区间的长度，遍历两个区间来确定差集元素。

3.并集算法 std::set_union

set_union - C++ Reference (cplusplus.com)

std::set_union 算法用于计算两个有序区间的并集。它会将两个有序区间中的元素合并，并去除重复元素，将结果存储到指定的目标区间中。

时间复杂度：该算法的时间复杂度为 O(n+m)，其中 n 和 m 分别是两个输入区间的长度。因为算法需要遍历两个区间的所有元素。