map
map 是 C++ STL 中的一种关联容器,用于存储键值对(key-value pairs)。每个键都是唯一的,可以通过键快速查找对应的值。下面是对 map 的详细讲解,包括其特性、用法和常见操作。
1. 基本特性
- 键值对:每个元素由一个键和一个对应的值组成,使用
pair 结构存储。
- 唯一性:每个键在
map 中是唯一的,如果插入一个已存在的键,则插入操作将无效(更新值)。
- 有序性:
map 中的元素是按键的顺序排列的,默认情况下使用键的升序排序。
- 自动平衡:内部使用红黑树实现,保证了查找、插入和删除操作的时间复杂度为 O(log n)。
map 的模板参数说明:

- key: 键值对中 key 的类型
- T: 键值对中 value 的类型
- Compare: 比较器的类型,map 中的元素是按照 key 来比较的,缺省情况下按照小于来比较,一般情况下 (内置类型元素) 该参数不需要传递,如果无法比较时 (自定义类型),需要用户自己显式传递比较规则 (一般情况下按照函数指针或者仿函数来传递)
- Alloc: 通过空间配置器来申请底层空间,不需要用户传递,除非用户不想使用标准库提供的空间配置器
注意:在使用 map 时,需要包含头文件。#include
2. 定义与初始化
map<int, string> myMap;
myMap[1] = "One";
myMap.insert({2, "Two"});
myMap.insert(make_pair(3, "Three"));
map<int, string> defaultMap;
vector<pair<int, string>> vec = {{1, "apple"}, {2, "banana"}, {3, "cherry"}};
map<int, string> rangeMap(vec.begin(), vec.end());
map<int, string> copiedMap(rangeMap);
map<int, string> movedMap(move(copiedMap));
map<int, string> initListMap = {{4, "date"}, {5, "elderberry"}};
3. 常见操作

插入元素
myMap[4] = "Four";
myMap.insert({5, "Five"});
-
insert() 方法:
insert() 方法是 std::map 或 std::set 的成员函数,用于插入元素。它接受一个元素或一个元素对 pair 作为参数,并将其插入到 map 或 set 中。
-
make_pair() 函数:
make_pair() 是一个辅助函数,用于构造一个 pair 对象。它的作用是方便地创建一个 pair,使得你可以将其作为参数传递给其他函数(例如 insert())。
两者的区别:
insert() 是插入操作,make_pair() 只是创建 pair:
insert() 负责将元素插入到容器中。
make_pair() 只是创建一个 pair,你可以将它用作 insert() 的参数,或者其他地方需要 pair 的地方。
- 使用场景:
insert() 用于实际的插入操作,它可以接受一个 pair、初始化列表或者其他容器。
make_pair() 用于方便地创建一个 pair,让你更简洁地写出键值对。
例子对比:
假设我们有一个 map<int, string>,并且我们想插入 {1, "One"} 和 {2, "Two"}:
使用 insert():
map<int, string> myMap;
myMap.insert({1, "One"});
myMap.insert({2, "Two"});
使用 make_pair():
map<int, string> myMap;
myMap.insert(make_pair(1, "One"));
myMap.insert(make_pair(2, "Two"));
这两种方式的效果是相同的,但 make_pair() 使得我们在某些情况下可以显式地创建 pair,尤其是当需要在函数中动态构造键值对时。
查找元素
删除元素
myMap.erase(3);
遍历元素
for (const auto& pair : myMap) {
cout << pair.first << ": " << pair.second << endl;
}
访问元素
1. operator[](下标运算符)访问:
- 功能:使用
operator[] 访问时,可以通过键来获取与之对应的值。
- 行为:
- 如果键存在,返回对应的值,并且你可以修改这个值。
- 如果键不存在,会自动插入一个新的键值对,其中键是你提供的键,而值会使用该类型的默认构造函数来创建。对于内置类型(如
int),默认值是 0,对于类类型,则会调用默认构造函数(例如,string 类型会初始化为 "",vector<int> 类型会初始化为空的 vector)。
- 优点:使用简单方便,适用于已知键存在或者可以接受自动插入默认值的情况。
- 缺点:如果访问一个不存在的键,
operator[] 会自动插入一个新的键值对,这可能会导致不希望的修改或插入。
2. at() 函数访问:
- 功能:
at() 函数也是用于通过键访问值,它与 operator[] 类似,区别在于它会抛出异常。
- 行为:
- 如果键存在,返回对应的值,并且你可以修改这个值。
- 如果键不存在,
at() 会抛出 out_of_range 异常,因此你需要使用 try-catch 来捕获这个异常。
- 优点:如果你不希望无意间插入新的键值对,
at() 提供了更安全的访问方式,因为它会在键不存在时抛出异常。
- 缺点:需要处理异常(
try-catch),如果你不处理异常,程序会崩溃。
区别总结:
| 特性 | operator[] | at() |
|---|
| 返回值 | 返回对应键的值(引用),可以修改 | 返回对应键的值(引用),可以修改 |
| 键存在时 | 返回对应的值,并可以修改 | 返回对应的值,并可以修改 |
| 键不存在时 | 自动插入一个新键值对,值为该类型的默认值 | 抛出 out_of_range 异常 |
| 插入行为 | 会插入新元素(如果键不存在) | 不会插入新元素 |
| 异常 | 无 | 会抛出 out_of_range 异常 |
4. 特殊用法
5. 代码示例
map<string, string> m;
m.insert(pair<string, string>("peach", "桃子"));
m.insert(make_pair("banan", "香蕉"));
m["apple"] = "苹果";
auto ret = m.insert(make_pair("peach", "桃色"));
if (ret.second) cout << "<peach, 桃色>不在 map 中,已经插入" << endl;
else cout << "键值为 peach 的元素已经存在:" << ret.first->first << "--->" << ret.first->second << " 插入失败" << endl;
m.erase("apple");
if (1 == m.count("apple")) cout << "apple 还在" << endl;
else cout << "apple 被吃了" << endl;
multimap
- Multimaps 是关联式容器,它按照特定的顺序,存储由 key 和 value 映射成的键值对<key, value>,其中多个键值对之间的 key 是可以重复的。
- 在 multimap 中,通常按照 key 排序和惟一地标识元素,而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同,通过 multimap 内部的成员类型 value_type 组合在一起,value_type 是组合 key 和 value 的键值对:
typedef pair<const Key, T> value_type;
- 在内部,multimap 中的元素总是通过其内部比较对象,按照指定的特定严格弱排序标准对 key 进行排序的。
- multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢,但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列。
- multimap 在底层用二叉搜索树 (红黑树) 来实现。
注意:multimap 和 map 的唯一不同就是:map 中的 key 是唯一的,而 multimap 中 key 是可以重复的。
- multimap 的使用
multimap 中的接口可以参考 map,功能都是类似的。
注意:
- multimap 中的 key 是可以重复的。
- multimap 中的元素默认将 key 按照小于来比较
- multimap 中没有重载 operator[] 操作 (同学们可思考下为什么?)。
- 使用时与 map 包含的头文件相同:
与 map 的不同
- 是否允许键重复
map:不允许键重复。每个键只能对应一个值。如果尝试插入具有相同键的键值对,插入操作会失败。
multimap:允许键重复。可以存储多个具有相同键的键值对。
2. 插入元素的行为
map:
- 如果插入一个已存在的键,则不会插入新值,而是保留原有值。
- 使用下标运算符
operator[] 可以方便地插入或修改键值对。
multimap:
- 每次插入都会创建一个新的键值对,即使键已存在。
- 不支持下标运算符
operator[],只能使用 insert 等方法插入数据。
3. 查找元素的行为
map:
find(key) 返回一个指向唯一键值对的迭代器。
- 如果键不存在,返回
end()。
multimap:
find(key) 返回指向第一个匹配键的迭代器。
- 如果键不存在,返回
end()。
- 可以使用
equal_range(key) 获取所有具有相同键的范围。
示例:
#include <iostream>
#include <map>
using namespace std;
int main() {
multimap<int, string> myMultiMap;
myMultiMap.insert({1, "One"});
myMultiMap.insert({1, "Another One"});
auto range = myMultiMap.equal_range(1);
for (auto it = range.first; it != range.second; ++it) {
cout << it->first << ": " << it->second << endl;
}
return 0;
}
输出:
1: One
1: Another One
4. 性能差异
- 在大多数操作(如插入、删除、查找)中,
map 和 multimap 的性能相似,因为它们都基于红黑树实现,时间复杂度为 O(log n)。
- 注意:
map 在插入重复键时会额外检查键是否已存在,因此插入操作可能略慢于 multimap。
multimap 由于允许重复键,无需进行唯一性检查,插入操作可能稍快。
5. 下标运算符
map:支持下标运算符 operator[],不仅可以用于访问,还可以用于插入数据。
multimap:不支持下标运算符,必须使用 insert 来插入数据。
6. 使用场景
map:适合用在键值唯一的场景,例如学生 ID 和姓名的对应关系。
multimap:适合用在键值可以重复的场景,例如学生分数和姓名的对应关系(可能有多个学生有相同分数)。
7. 总结对比表
| 特性 | map | multimap |
|---|
| 是否允许键重复 | 否 | 是 |
| 插入行为 | 相同键覆盖旧值 | 每次插入新键值对 |
下标运算符 ([]) | 支持 | 不支持 |
| 查找行为 | 返回唯一键值对 | 返回第一个匹配键,并支持范围查找 |
| 性能 | 插入稍慢(需检查唯一性) | 插入稍快(无唯一性检查) |
| 适用场景 | 键唯一的场景 | 键重复的场景 |
multimap 与 multiset 为何不提供 []
multimap 和 multiset 都不提供 operator[] 操作符,主要原因在于它们的特性和设计目的。
-
multimap 不提供 operator[] 的原因
map 中的 operator[] 允许通过键来访问值,并在键不存在时自动插入一个具有默认值的键值对。这是基于 map 的单一键值映射的设计原则:每个键都唯一,只映射到一个值。这种语法对 map 很自然,但对 multimap 不适用。
在 multimap 中,每个键可以对应多个值(即允许重复键)。因此,如果 multimap 提供 operator[],就会产生以下问题:
- 不明确的语义:
operator[] 应该返回哪个值?因为同一个键可能映射到多个值,直接通过 operator[] 查找不具有确定性。
- 违背设计逻辑:
operator[] 通常在键不存在时会插入默认值,但 multimap 不希望如此,因为它的设计初衷是支持键的多对一映射,而不是默认的单一键值对。
因此,为了避免模糊性,multimap 只提供了插入和查找方法(如 insert 和 equal_range 等),而没有 operator[] 的支持。
-
multiset 不提供 operator[] 的原因
multiset 是一个不允许重复键的集合,且元素本身没有任何'值'可以通过 operator[] 修改。multiset 中的每个元素都是独立的,不像 map 中的键值对那样具备'键 - 值'结构,因此使用 operator[] 并无意义。
在 multiset 中,元素可以多次插入,并且插入的只是一个值(没有键对应的映射值),因此:
- 无键 - 值结构:
operator[] 在 multiset 中不适用,因为没有'键'可以进行查找,也没有'值'可以访问或修改。
- 不支持默认插入:
operator[] 通常会在键不存在时插入默认值,这与 multiset 的集合概念不符。
因此,multiset 和 multimap 都没有实现 operator[],而是提供了插入、查找、删除等符合集合语义的方法,以更好地符合它们的设计初衷。
在 OJ 题中的使用
138. 随机链表的复制
(https://leetcode.cn/problems/copy-list-with-random-pointer/)


解法 1
这段代码的主要思路是利用哈希表来建立原节点与新节点的映射关系,进而完成链表的深拷贝。整个流程分为两步:
- 创建拷贝链表的节点及其
next 指针:遍历原链表,创建每个节点的新拷贝节点,将新节点插入拷贝链表中。并使用一个哈希表 nodeMap 来存储原节点和新节点之间的对应关系。
- 复制
random 指针:再次遍历链表,对于每个节点,利用 nodeMap 映射找到其 random 指针指向的新节点,并完成新链表中的 random 指针的设置。
代码解读与注释
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) { val = _val; next = nullptr; random = nullptr; }
};
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> nodeMap;
Node* copyhead = nullptr;
Node* 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;
}
nodeMap[cur] = copytail;
cur = cur->next;
}
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;
}
copyhead;
}
};
解法评价
- 优点:此方法利用哈希表来存储原链表节点与新节点的对应关系,简单明了,适合理解和调试。通过两次遍历链表,能够准确地复制所有的
next 和 random 指针。
- 时间复杂度:O(n),其中 n 是链表节点数。两次遍历的总时间复杂度是线性的。
- 空间复杂度:O(n),主要是用来存储
nodeMap 哈希表,该表的大小和链表的节点数成正比。
注意点
- 使用
nodeMap 保存原链表节点与拷贝链表节点的映射,确保 random 指针指向的是新链表的对应节点,而不是原链表节点。
nodeMap[cur->random] 可以直接访问到对应的拷贝节点,大大简化了查找 random 指针的复杂度。
解法 2:回溯 + 哈希表
这个解法通过回溯 + 哈希表的方式进行链表深拷贝,使用了递归的思路,将原链表中的每一个节点都独立地复制。因为链表中存在随机指针(random),导致在复制某节点时,可能指向的节点还没有被创建,所以需要特别处理。这个方法的核心是利用递归回溯和哈希表,以确保所有节点都只被创建一次。
解法思路
具体流程如下:
- 哈希表保存映射关系:为了保证每个节点只被复制一次,定义一个哈希表
cachedNode,其中 key 是原链表中的节点,value 是对应的复制节点。这样就可以快速查询一个节点是否已经复制过。
- 递归创建复制节点:
- 如果传入的节点为空,返回
nullptr,表示递归到达链表尾部,结束递归。
- 否则,检查哈希表
cachedNode 中是否存在这个节点:
- 未复制过:说明当前节点没有被创建,那么就创建一个新节点,将其值设为原节点的值,将其保存到
cachedNode 中,并继续递归创建当前节点的 next 和 random 指针指向的节点。
- 已复制过:直接从哈希表
cachedNode 中返回该节点的引用,避免重复创建。
- 回溯并赋值:递归调用返回时,将
next 和 random 指针设置为新链表中的对应节点。通过回溯的方式,逐层构造链表并完成指针的连接。
- 最终返回头节点:返回深拷贝链表的头节点即可。
代码分析与注释
class Solution {
public:
unordered_map<Node*, Node*> cachedNode;
Node* copyRandomList(Node* head) {
if (head == nullptr) {
return nullptr;
}
if (!cachedNode.count(head)) {
Node* headNew = new Node(head->val);
cachedNode[head] = headNew;
headNew->next = copyRandomList(head->next);
headNew->random = copyRandomList(head->random);
}
return cachedNode[head];
}
};
具体例子分析
假设链表中有三个节点 A、B、C,链表结构如下:
- A 指向 B,B 指向 C
- A 的
random 指针指向 C,B 的 random 指针指向 A,C 的 random 指针为空。
在调用 copyRandomList(A) 时的递归过程:
A 未被复制过,创建 A',并将 A -> A' 映射存入 cachedNode。
- 开始递归创建
A 的 next 节点 B 的拷贝,调用 copyRandomList(B)。
B 未被复制过,创建 B',并将 B -> B' 映射存入 cachedNode。
- 开始递归创建
B 的 next 节点 C 的拷贝,调用 copyRandomList(C)。
C 未被复制过,创建 C',并将 C -> C' 映射存入 cachedNode。
C 的 next 为 nullptr,因此 C' 的 next 也设为 nullptr,同时 C.random 为 nullptr,所以 C'.random 也设为 nullptr。
- 回溯到
B,将 B' 的 next 设为 C',并递归 B.random 指向的 A,返回 A' 作为 B'.random。
- 回溯到
A,将 A' 的 next 设为 B',并递归 A.random 指向的 C,返回 C' 作为 A'.random。
最终返回 A',构造出的链表为拷贝的链表。
评价
- 优点:通过哈希表来记录原节点与新节点的映射关系,有效防止了重复创建节点,且借助回溯的思路使得指针的拷贝逻辑非常清晰。
- 时间复杂度:O(n),需要遍历整个链表一次,并创建 n 个节点。
- 空间复杂度:O(n),主要是哈希表
cachedNode 所占用的空间。
总结
这种方法简洁且具有通用性,通过回溯实现了深拷贝,适合处理链表中复杂指针关系的深拷贝问题。
这个代码中的递归过程其实并没有显式地表现出'回溯'的操作,它主要是递归地调用自身来构建新链表。在这里,回溯体现在递归函数的'逐层返回'上。
代码中的'回溯'原理
让我们从递归调用的角度来解释这个代码的执行过程。在链表的每一层递归调用中,代码会递归地构建当前节点的 next 和 random 指针指向的节点,然后逐层返回,把构建好的节点组装成一个完整的链表。
在递归调用时,当前函数会等待 copyRandomList(head->next) 和 copyRandomList(head->random) 递归调用完成,才能继续执行剩下的代码。由于每层递归都创建新节点并把它放入 cachedNode 中,当回到上层时,可以直接从 cachedNode 中取出新节点,避免重复创建。
示例解析
假设链表结构如下:
head -> Node1 (val = 1, random -> Node3)
|
v
Node2 (val = 2, random -> Node1)
|
v
Node3 (val = 3, random -> Node2)
执行步骤如下:
- 第一个节点
Node1:调用 copyRandomList(Node1)。
Node1 未拷贝过,创建新节点 Node1_copy。
- 对
Node1->next 调用 copyRandomList(Node2),递归进入 Node2 的拷贝。
- 第二个节点
Node2:递归进入 copyRandomList(Node2)。
Node2 未拷贝过,创建新节点 Node2_copy。
- 对
Node2->next 调用 copyRandomList(Node3),递归进入 Node3 的拷贝。
- 第三个节点
Node3:递归进入 copyRandomList(Node3)。
Node3 未拷贝过,创建新节点 Node3_copy。
Node3->next 为空,返回 nullptr。
- 对
Node3->random 调用 copyRandomList(Node2),检查发现 Node2_copy 已存在于 cachedNode 中,直接返回。
- 返回
Node3_copy:从 Node3_copy 返回上一层递归。
- 此时
Node2_copy->next = Node3_copy。
- 对
Node2->random 调用 copyRandomList(Node1),检查发现 Node1_copy 已存在,直接返回。
- 返回
Node2_copy:从 Node2_copy 返回上一层递归。
- 此时
Node1_copy->next = Node2_copy。
- 对
Node1->random 调用 copyRandomList(Node3),检查发现 Node3_copy 已存在,直接返回。
- 返回
Node1_copy:所有递归完成,返回 Node1_copy,即为复制链表的头节点。
为什么这体现了回溯
在每一层递归中,函数会处理当前节点并尝试向下构建 next 和 random 指针的节点。递归调用完成后,代码会逐层返回,逐步完成链表节点的组装。所以,'回溯'体现在递归调用完成后逐层返回并把结果逐层组装的过程,它不是显式的'返回上一步'操作,而是递归逐层完成的自然返回。
回溯和递归的区别
回溯和递归是两个相关但有区别的概念。
- 递归:是一种编程技巧,指的是函数调用自身的过程。在解决问题时,如果问题可以分解为相似的子问题,我们可以用递归来简化代码。递归的核心是不断分解问题,直到达到基准条件(或称递归终止条件),然后逐层返回结果。例如,阶乘、斐波那契数列计算等都可以使用递归来实现。
- 回溯:是一种算法策略,常用于搜索问题的解空间,比如求解排列、组合、图的路径、迷宫等问题。回溯也用到了递归,但它的核心在于试探和撤回,即尝试去求解一个问题,如果当前路径行不通就返回上一步,尝试其他路径,直到找到一个解或所有路径都尝试完为止。它的关键是'回头走'——如果当前选择不满足条件,就回退一步选择新的分支。
区别
- 递归是技术,用来实现算法逻辑中的逐层调用。
- 回溯是一种算法策略,通常使用递归来实现。回溯是递归的一种应用,但不仅限于递归,也可以用迭代实现。
举个例子
在复制随机链表这类问题中,使用递归的过程只是在链表中逐层递归创建节点;而在组合、排列等问题中使用回溯时,通常需要尝试多条分支路径并在不满足条件时返回,这就是回溯的过程。
692. 前 K 个高频单词
题目链接

仿函数(Functor)
仿函数(Functor)是指可以像普通函数一样调用的对象。在 C++ 中,仿函数是通过重载 operator() 来实现的,即将类或结构体的对象变成'可调用'的对象,使得该对象可以像函数一样被使用。
在传统的面向对象编程中,类的对象不能像函数那样直接调用,而仿函数通过实现一个特殊的成员函数 operator(),使得类的对象具有类似函数的行为。
仿函数的定义与使用
1. 定义仿函数:
仿函数是通过定义一个包含 operator() 操作符的类或结构体来实现的。这个 operator() 可以有零个或多个参数,甚至返回值。我们可以在仿函数中实现任何想要的功能。
#include <iostream>
using namespace std;
class Adder {
public:
int operator()(int a, int b) {
return a + b;
}
};
int main() {
Adder add;
cout << add(3, 4) << endl;
return 0;
}
输出:
7
在上面的例子中,Adder 类定义了 operator(),使得 add 对象能够像一个普通函数一样被调用,add(3, 4) 实际上是调用了 Adder 类中的 operator()(int a, int b)。
2. 使用仿函数:
仿函数常见的应用场景包括:
- 算法中的自定义操作:在 STL 算法(如
std::sort, std::for_each 等)中,我们可以使用仿函数传递给算法进行自定义操作。
- 回调函数:仿函数可以作为回调函数,在执行一些操作时执行用户定义的功能。
- 函数对象代替函数指针:仿函数比普通的函数指针更灵活,因为它不仅能传递行为,还能包含状态信息。
仿函数的优势
- 封装了行为:仿函数是一个类或结构体,可以拥有成员变量和成员函数。可以封装和存储状态信息。相比之下,普通函数只能接受参数并返回结果,不能存储额外的状态。
- 可以重载
operator():仿函数可以像普通函数一样调用,但它还能有更丰富的功能。通过重载 operator(),仿函数可以接受不同的参数类型,也可以有不同的行为。
- 支持状态:仿函数是类的实例,它们可以拥有成员变量,从而支持存储状态。这对于某些需要记住状态的操作(如计数器、累加器等)非常有用。
- 与 STL 算法结合使用:STL 算法(如
std::sort, std::for_each 等)经常需要传入某些操作。使用仿函数可以使得操作更加灵活,仿函数可以是带状态的,因此能适应复杂的需求。
仿函数与普通函数的对比
- 普通函数:普通函数是独立的,不具有状态。每次调用时需要传递所有必要的参数。
- 仿函数:仿函数是类的成员,可以拥有状态和行为。可以在调用时动态改变它的状态,具有更强的灵活性。
示例:使用仿函数进行排序
下面是一个使用仿函数与 std::sort 一起排序的例子:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Compare {
public:
bool operator()(int a, int b) {
return a > b;
}
};
int main() {
vector<int> vec = {1, 5, 3, 9, 2};
sort(vec.begin(), vec.end(), Compare());
for (int num : vec) {
cout << num << " ";
}
return 0;
}
输出:
9 5 3 2 1
在这个例子中,Compare 类定义了一个排序规则(从大到小)。通过重载 operator(),我们将该类变成了一个仿函数,可以传递给 std::sort 来控制排序的顺序。
仿函数的应用
- 函数对象:仿函数可以作为函数对象传递给 STL 算法,例如
std::sort、std::transform 等。
- 自定义排序规则:仿函数常常用来定义自定义的排序规则,作为
std::sort 的第三个参数。
- 事件处理/回调:在事件驱动编程或回调函数的场景中,仿函数作为事件处理的实现,或者作为回调传递。
- 缓存和状态管理:仿函数可以存储和管理状态,例如计数器、缓存等。
总结
仿函数是通过重载 operator() 使得类的对象具备了像函数一样的调用能力。在 C++ 中,仿函数常用于 STL 算法中,通过它们可以在算法中传递自定义操作,具备更高的灵活性和状态管理能力。
解法 1:
class Solution {
public:
struct KVCompare {
bool operator()(const pair<string, int>& kv1, const pair<string, int>& kv2) {
if (kv1.second == kv2.second) {
return kv1.first < kv2.first;
}
return kv1.second > kv2.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(), KVCompare());
vector<string> res;
auto it = v.begin();
while (k--) {
res.push_back(it->first);
it++;
}
res;
}
};
在 C++ 中,仿函数(或称为函数对象)是一种重载了 operator() 的对象,可以像普通函数一样被调用。仿函数的定义可以使用结构体或类,两者的功能是相同的。这里使用结构体的原因主要是出于简化和代码风格的考虑。
仿函数为什么可以用结构体?
仿函数(函数对象)本质上是一个包含重载了 operator() 的对象,而这个对象的实现可以使用结构体或类。对于这种场景来说,结构体和类的主要区别在于:结构体的默认访问控制是 public,而类的默认访问控制是 private。结构体通常用于只包含数据的简单对象,结构体的成员通常是 public,而类用于包含更多封装逻辑和行为。
由于仿函数的定义通常较简单,只有一个 operator() 成员函数和一些数据成员(如果需要的话),所以很多时候选择使用结构体来定义仿函数,这样代码更加简洁且清晰。
仿函数用结构体的优势简洁性:结构体的默认成员是 public,如果仿函数只需要暴露一个公共函数(例如 operator()),使用结构体比类更简洁,避免了显式地声明成员为 public。代码风格:在 C++ 中,通常用结构体来表示简单的数据结构或行为,而用类来表示封装性更强、包含更多功能和内部状态的对象。因此,如果仿函数只是为了提供一个简单的排序规则,结构体显得更为符合这种简洁的风格。
例子:仿函数使用结构体的情况
你给出的例子就是使用结构体来定义仿函数,它负责根据 pair<string, int> 中的 int 值进行降序排序,如果出现次数相同则按 string 的字典顺序升序排序。
这里,结构体 KVCompare 重载了 operator(),使得它能够作为一个仿函数传递给 STL 容器(如 priority_queue)来定制排序规则。
结构体与类的选择
如果你将来需要为仿函数添加更多的成员变量或成员函数,或者你希望更好地控制访问权限(例如把成员设置为 private),可以使用类。而如果仿函数非常简单且只包含公共成员,使用结构体会使代码更加清晰和简洁。
使用结构体的情况:只需要包含一个或少量的成员函数。不需要复杂的封装和访问控制。优先考虑简洁和可读性。
使用类的情况:需要复杂的封装和数据管理。成员函数较多,或者需要维护内部状态。需要控制数据成员的访问权限(例如使用 private、protected)。
解法 2:优先队列
这种解法的核心思路是使用优先队列(Priority Queue)来找到前 k 个频率最高的单词。优先队列能够高效地支持对最大值(或最小值)的快速查询和删除,因此非常适合用于这类问题。
详细思路:
- 统计单词频率:
- 我们首先用
unordered_map 来统计每个单词在 words 中的出现次数。unordered_map<string, int> 可以在平均 O(1) 时间内插入和查找元素。
- 创建一个优先队列:
- 使用一个小根堆(min-heap)来管理频率最高的 k 个单词。小根堆的特点是堆顶元素是最小的元素,这样可以确保堆中最多只有 k 个元素,当堆的大小超过 k 时,我们可以删除堆顶(即出现频率最小的元素)。
- 比较规则:
- 在优先队列中,元素是单词和它们出现次数的
pair。我们用自定义的比较器 cmp 来控制堆的排序规则:
- 如果两个单词的出现次数相同,那么我们按字典顺序升序排列(即较小的单词排在前面)。
- 如果两个单词的出现次数不同,频率较高的单词排在前面(即频率较大的元素优先)。
- 插入到优先队列:
- 对于
unordered_map 中的每一个单词及其频率,我们将其插入到优先队列中。
- 每插入一个新元素后,如果优先队列的大小超过了 k,我们就弹出堆顶元素(即删除出现频率最低的元素)。这样优先队列中始终保持着出现频率前 k 高的元素。
- 获取结果:
- 最后,优先队列中的元素就是出现次数最多的 k 个单词,但它们的顺序可能是从频率最低到最高的,因此需要通过逐个弹出堆顶元素的方式来得到按频率排序的前 k 个单词。
- 注意:
- 最终返回的是一个包含 k 个单词的向量,要求按频率排序,如果频率相同则按字典顺序排列。
代码解析:
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
unordered_map<string, int> cnt;
for (auto& word : words) {
cnt[word]++;
}
auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
return a.second == b.second ? a.first < b.first : a.second > b.second;
};
priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
for (auto& it : cnt) {
que.emplace(it);
if (que.size() > k) {
que.pop();
}
}
vector<string> ret(k);
for (int i = k - 1; i >= 0; i--) {
ret[i] = que.top().first;
que.pop();
}
return ret;
}
};
详细步骤:
- 统计单词频率:
unordered_map<string, int> cnt;
for (auto& word : words) {
cnt[word]++;
}
- 这段代码统计了
words 数组中每个单词的出现次数。unordered_map 是一个哈希表,它能够在常数时间内完成查找和插入。
- 创建优先队列:
auto cmp = [](const pair<string, int>& a, const pair<string, int>& b) {
return a.second == b.second ? a.first < b.first : a.second > b.second;
};
priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> que(cmp);
- 这里定义了一个 lambda 表达式
cmp,用来比较两个单词频率的大小:
- 如果频率相同,则按字典顺序升序排列。
- 如果频率不同,则按频率降序排列。
- 接着使用该比较规则定义了一个小根堆
que,这个优先队列的元素类型是 pair<string, int>,即单词及其出现次数。
- 插入元素并维护堆的大小:
for (auto& it : cnt) {
que.emplace(it);
if (que.size() > k) {
que.pop();
}
}
- 对于
cnt 中的每个元素(即每个单词及其频率),我们将它插入优先队列 que 中。
- 如果优先队列的大小超过了 k,我们就弹出堆顶元素,这样保证优先队列中最多只保留 k 个频率最高的单词。
- 从优先队列中取出前 k 个元素:
vector<string> ret(k);
for (int i = k - 1; i >= 0; i--) {
ret[i] = que.top().first;
que.pop();
}
return ret;
- 最后,我们逐个从优先队列中取出单词(按频率从高到低),将它们存放到
ret 向量中,并返回结果。
时间复杂度:
- 统计频率:
unordered_map 的插入操作平均时间复杂度是 O(1),因此统计频率的时间复杂度是 O(n),其中 n 是 words 的长度。
- 优先队列插入:对于每个单词的频率,我们都要插入优先队列。每次插入的时间复杂度是 O(log k),因为队列中最多只能有 k 个元素。因此插入所有单词的时间复杂度是 O(n log k)。
- 取出 k 个元素:最后从优先队列中取出 k 个元素,每次取出操作是 O(log k),因此取出所有 k 个元素的时间复杂度是 O(k log k)。
349. 两个数组的交集
题目链接
解法 1:set 去重
解法思路
这道题的核心任务是找出两个数组中的公共元素,且每个元素只能出现一次。解决思路如下:
- 去重:可以使用
set 数据结构,因为 set 自动去重。
- 查找交集:通过将两个数组转换为
set,可以很方便地进行交集操作。可以遍历一个 set,在另一个 set 中查找是否存在相同的元素。
代码解释
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());
vector<int> ret;
for (auto e : s2) {
if (s1.count(e)) {
ret.push_back(e);
}
}
return ret;
}
};
代码详细解析
- 去重操作:
set<int> s1(nums1.begin(), nums1.end());
set<int> s2(nums2.begin(), nums2.end());
set<int> 是一个自动去重的容器,能够保证每个元素只出现一次。这里,我们将 nums1 和 nums2 转换为两个 set,这样就自动去除了数组中的重复元素。
set 的元素会自动按照升序排列(虽然题目没有要求顺序,但它的这一特性有时能帮助我们优化某些问题)。
- 查找交集:
for (auto e : s2) {
if (s1.count(e)) {
ret.push_back(e);
}
}
- 通过遍历
s2 中的每个元素 e,我们检查 s1 中是否包含该元素。这里使用了 set 提供的 count() 方法,set.count(e) 会在 set 中查找元素 e,如果找到,则返回 1,否则返回 0。
- 如果
s1.count(e) 为真,说明 e 是 nums1 和 nums2 的共同元素,就把它添加到结果数组 ret 中。
- 返回结果:
return ret;
- 最后返回交集元素的集合
ret,即包含 nums1 和 nums2 中公共元素的数组。
时间复杂度分析
- 将数组
nums1 转换为 set:时间复杂度为 O(n),其中 n 是 nums1 的元素个数。
- 将数组
nums2 转换为 set:时间复杂度为 O(m),其中 m 是 nums2 的元素个数。
- 遍历
s2 中的每个元素并在 s1 中查找:对于每个元素 e,查找操作的时间复杂度是 O(1)(因为 set 中的查找是常数时间)。所以,这一部分的时间复杂度为 O(m)。
因此,整个算法的时间复杂度为 O(n + m),其中 n 是 nums1 的大小,m 是 nums2 的大小。
空间复杂度分析
- 我们使用了两个
set 来存储 nums1 和 nums2 中的元素,因此空间复杂度是 O(n + m)。
- 另外,还用了一个
vector 来存储结果集,因此空间复杂度总的来说是 O(n + m)。
解法 2-双指针法
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());
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;
}
};
代码解释:
set<int> s1(nums1.begin(), nums1.end()) 和 set<int> s2(nums2.begin(), nums2.end()):将两个输入数组转换为 set,这会自动去除重复的元素,并将元素排序。
- 双指针遍历
set:使用两个指针 it1 和 it2 分别指向两个 set 的开始位置,进行比较。
- 如果
*it1 < *it2,说明 it1 指向的元素小,应该将 it1 向后移动。
- 如果
*it1 > *it2,说明 it2 指向的元素小,应该将 it2 向后移动。
- 如果
*it1 == *it2,说明找到了交集元素,将其加入结果中,并同时移动两个指针。
- 返回交集结果:最终返回
ret,即两个数组的交集。
复杂度分析:
- 时间复杂度:
- 将两个数组转换为
set 的时间复杂度是 O(n log n + m log m),其中 n 和 m 分别是两个数组的长度。
- 双指针遍历两个
set 的时间复杂度是 O(n + m),因为每个指针最多遍历一次。
- 总时间复杂度为 O(n log n + m log m),其中 n 和 m 是输入数组的大小。
- 空间复杂度:
- 存储
set 的空间复杂度是 O(n + m),即两个 set 中的元素总数。
- 最终返回的
ret 向量最多包含两个数组中交集的元素,空间复杂度为 O(min(n, m))。
因此,总体空间复杂度为 O(n + m)。
这个解法的主要优势在于:
- 使用
set 自动去重,简化了代码。
- 双指针法高效地找到了交集元素,避免了暴力算法的时间复杂度问题。