Skip to content

数据结构与算法 ​


一、复杂度与选型总表 ​

1. 复杂度速查 ​

Q: 常见复杂度从低到高怎么排?实际性能只看大 O 吗?

大 O 只描述增长趋势,常数和缓存局部性会改变实际胜负——同样是 O(n),vector 往往比 list 快一个数量级(见 §一.3)。

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)。

2. 各结构操作复杂度总表 ​

结构查找插入删除有序典型用途
数组O(1) 下标 / O(n) 值O(n)O(n)否连续存储、随机访问
vectorO(1) 下标 / O(n) 值尾部均摊 O(1),中间 O(n)尾部 O(1),中间 O(n)否默认容器
链表O(n)O(1)(已知位置)O(1)(已知位置)否频繁中间插删、引用稳定
dequeO(1)头尾 O(1),中间 O(n)头尾 O(1),中间 O(n)否队列、滑动窗口
栈 / 队列仅顶 / 队首 O(1)O(1)O(1)否LIFO / FIFO
哈希表平均 O(1),最坏 O(n)平均 O(1),扩容 O(n)平均 O(1)否纯查找、去重
红黑树 map/setO(log n)O(log n)O(log n)是有序、范围查询
跳表平均 O(log n),最坏 O(n)平均 O(log n)平均 O(log n)是Redis zset
堆极值 O(1),任意值 O(n)O(log n)O(log n)偏序TopK、定时器
BST 二叉搜索树平均 O(log n),最坏 O(n)平均 O(log n)平均 O(log n)是有序动态集
AVL / 红黑树O(log n)O(log n)O(log n)是平衡有序集
B+ 树O(log_m n)O(log_m n)O(log_m n)是磁盘索引
TrieO(L),L 为串长O(L)O(L)前缀有序前缀匹配
并查集近似 O(1)(α(n))近似 O(1)近似 O(1)否连通性

易错点:堆只有堆顶是 O(1),查找任意元素仍是 O(n);红黑树和哈希表都能去重,但只有红黑树能按顺序遍历。

3. 缓存友好性:数组为什么常胜链表 ​

Q: 都说链表插入 O(1),为什么工程里还是优先用 vector?

因为链表的 O(1) 前还有一个隐藏的 O(n) 定位,而定位过程缓存极不友好。

  • CPU 按 64 字节缓存行加载数据,数组顺序访问内核会触发设备到内核缓冲区的缓存,一次 cache miss 能摊到十几个元素上。
  • 链表节点分散在堆上,每走一步都可能是一次 cache miss(缓存失效需要重新在设备中读)。
  • 因此遍历 vector 通常比 list 快 5~10 倍;即使中间插入,vector 的大块 memmove 也常常快过链表的逐个找位置。

选型准则:默认 vector;只有在「已经持有迭代器、频繁中间插删、且需要引用 / 迭代器稳定」时才用 list。

4. 均摊分析 ​

Q: vector::push_back 均摊 O(1) 是怎么来的?某一次为什么可能是 O(n)?

按 2 倍扩容时,插入 n 个元素的总搬运次数为 1 + 2 + 4 + ... + n < 2n,摊到 n 次插入上就是 O(1)。

  • 哈希表 rehash 同理:一次迁移 n 个元素,摊到 n 次插入仍是 O(1)。
  • 均摊 ≠ 每次:触发扩容的那一次确实要 O(n);对延迟敏感的实时系统应提前 reserve。

二、线性结构 ​

1. 数组 vs 链表 ​

Q: 数组和链表各自适合什么场景?

维度数组 / vector链表
内存布局连续分散,每个节点额外存指针
随机访问O(1)O(n)
中间插删O(n)(要搬移)O(1)(已知位置)
缓存友好好差
迭代器 / 引用稳定性扩容后全失效除被删节点外稳定
典型场景绝大多数场景频繁 splice、引用稳定

链表三大基本功:

  1. dummy 哨兵:头节点可能被删 / 被换时,用 dummy.next = head 统一处理。
  2. 快慢指针:找中点、判环、找环入口、找倒数第 k 个。
  3. 三指针:反转链表时 prev / cur / next 缺一不可,先存 next 再改指针。

2. vector 底层与扩容 ​

Q: vector 的底层结构是什么?size 和 capacity 有什么区别?

三个指针:

text
start_          finish_              end_of_storage_
  |                |                       |
  v                v                       v
+----+----+----+----+----+----+----+----+
| 1  | 2  | 3  |    |    |    |    |    |
+----+----+----+----+----+----+----+----+
  <---- size ----> <---- 未构造 ---->
  <-------------- capacity ------------->
  • size() = finish_ - start_:已构造元素个数。
  • capacity() = end_of_storage_ - start_:已申请内存能容纳的个数。
  • 扩容流程:申请新内存 → 搬移旧元素 → 析构并释放旧内存。libstdc++ 按 2 倍,MSVC 按 1.5 倍,目的都是让均摊 O(1)。
操作作用常见坑
reserve(n)只改 capacity,不改变 size越界访问仍是 UB
resize(n)改 size,多出的元素值初始化 / 析构会真正构造对象
clear()size 置 0不释放 capacity
emplace_back(args)原地构造,省一次临时对象参数要能直接构造 T
push_back(v)先构造 v 再移动 / 拷贝有移动构造时开销已很小

实现见 01_动态数组.cpp。

3. vector 迭代器失效 ​

Q: vector 哪些操作会导致迭代器失效?

操作失效范围说明
push_back / emplace_back未扩容:end();扩容:全部扩容后元素地址全变
reserve重新分配则全部capacity 变大也可能搬移
insert / erase插入 / 删除点及其之后后面的元素整体搬移
resize扩容则全部

准则:修改容器后重新获取迭代器;循环中删除用 it = v.erase(it);需要跨修改保存位置时用下标而不是迭代器。

4. list 与 deque 底层 ​

Q: list 和 deque 的底层是什么?为什么 queue 默认用 deque?

list:双向链表,节点存 prev / next / value。

  • 已知位置的插入 / 删除 O(1)
  • list::sort 用的是归并排序(链表做不到随机访问)。
  • 除被删除节点外,迭代器和引用都稳定;代价是每节点两个指针、缓存极差。

deque:中控 map + 固定大小缓冲区(libstdc++ 每块 512 字节)。

  • 头尾插入 / 删除均摊 O(1);随机访问 O(1),但要经过「中控数组 → 缓冲区」两次间接。
  • 迭代器失效规则特殊:头尾插入只失效迭代器,引用 / 指针仍有效;中间插入使全部失效。
  • queue 需要 O(1) 的 pop_front,vector 做不到,所以标准选择 deque;
  • stack 理论上可用 vector(缓存更好),但标准统一用 deque。

5. 栈与队列 ​

Q: 栈和队列分别有哪些典型应用?

结构典型应用
栈括号匹配、表达式求值(操作数栈 + 运算符栈)、函数调用栈、DFS、撤销
队列BFS、任务队列、消息队列、滑动窗口、生产者-消费者缓冲区

循环队列判满:容量为 cap 的数组,常用 (tail + 1) % cap == head 判满,代价是牺牲一个槽位;也可以额外维护 size 计数,避免浪费。

6. 单调栈与单调队列 ​

Q: 单调栈 / 单调队列解决什么问题?为什么是 O(n)?

单调栈:求「下一个更大 / 更小元素」、接雨水、柱状图最大矩形。

cpp
// 下一个更大元素:维护一个从栈底到栈顶递减的栈
vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> res(n, -1);
    stack<int> st;                       // 存下标
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && a[st.top()] < a[i]) {
            res[st.top()] = a[i];
            st.pop();
        }
        st.push(i);
    }
    return res;
}

单调队列:滑动窗口最大值。队列存下标,保证值从队首到队尾递减;队首过期就弹出,新元素入队前从队尾弹掉更小的。

cpp
// 滑动窗口最大值:单调队列(队头—队尾 递减)
// k:滑动窗口的大小
// res:存每个窗口的最大值
vector<int> maxSlidingWindow(vector<int>& a, int k) {
    int n = a.size();
    vector<int> res;
    deque<int> dq;                       // 存下标
    for (int i = 0; i < n; ++i) {
        // 1) 队头过期(滑出窗口)
        if (!dq.empty() && dq.front() <= i - k)
            dq.pop_front();
        // 2) 队尾维护单调递减 (新元素进队前,把队尾比它小的全踢掉,哪怕踢空)
        // 为什么不从队头开始?因为队列是"下标递增 + 值递减",所以"又新又小、会被新元素压掉"的必然堆在队尾
        while (!dq.empty() && a[dq.back()] < a[i])
            dq.pop_back();
        dq.push_back(i);
        // 3) 窗口成型后输出队头(当前最大)
        if (i >= k - 1) res.push_back(a[dq.front()]);
    }
    return res;
}
  • 每个元素最多进队一次、出队一次,所以是 O(n)。
  • 典型题:滑动窗口最大值、最短子数组、接雨水。

7. 环形队列与 SPSC ​

Q: 环形队列怎么判空判满?无锁 SPSC 队列靠什么保证正确?

  • 判空判满:head == tail 表示空;若用「牺牲一个槽位」法,(tail + 1) & mask == head 表示满。
  • SPSC(单生产者单消费者)无锁:生产者只写 tail,消费者只写 head,各自读对方的下标。
    • 自己写的下标用 relaxed;发布数据用 release;读取对方下标用 acquire,形成 happens-before。
  • 工程落点:io_uring 的 SQ / CQ 环、日志系统的双 buffer、线程池任务队列。

实现见 20_无锁环形队列.cpp;伪共享靠 alignas(64) 把两个下标分到不同缓存行,内存序只需记住「写端 release、读端 acquire」的配对。

8. 链表高频手撕 ​

Q: 链表题有哪些固定套路?

题目关键点
反转链表prev / cur / next 三指针,先存 next 再改指向
判断有环快慢指针,相遇即有环
找环入口相遇后一个指针回到 head,两指针同速再相遇即入口
合并两个有序链表dummy 哨兵 + 尾指针
删除倒数第 k 个快指针先走 k 步,再同步走
相交链表长度差对齐;或双指针走完各自换头,总路程相等
复制带随机指针的链表哈希表存「原节点 → 新节点」;或穿插复制后拆链
K 个一组翻转dummy + 每组先找尾 + 组内反转 + 接回
链表排序快慢指针找中点 + 归并,O(n log n)、O(1) 额外空间
回文链表找中点 + 反转后半 + 比较(可再反转恢复)

实现见 02_链表.cpp。

9. KMP ​

Q: KMP 的 next / pi 数组是什么含义?为什到 O(n+m)?

pi[i] 表示 pat[0..i] 的最长相等真前缀 / 真后缀长度。

  • 暴力匹配失配时文本指针要回退,最坏 O(nm)。
  • KMP 失配时文本指针 i 不回退,只把模式串指针 j 跳到 pi[j-1],利用已经匹配过的信息。
  • 预处理 O(m),匹配 O(n),总 O(n+m);空间 O(m)。
cpp
// 构建 pi
vector<int> pi(m, 0);
for (int i = 1, j = 0; i < m; ++i) {
    while (j > 0 && pat[i] != pat[j]) j = pi[j - 1];
    if (pat[i] == pat[j]) ++j;
    pi[i] = j;
}

应用:子串查找;最短循环节 n - pi[n-1](若 n % (n - pi[n-1]) == 0 则由该节循环构成)。

实现见 24_KMP算法.cpp。


三、哈希 ​

1. 哈希表原理与冲突 ​

Q: 哈希冲突有哪些解决方案?链地址法和开放定址法怎么选?

链地址法开放定址法
做法每个桶挂一个链表 / 红黑树冲突后按规则探测下一个空位
装载因子可以 > 1必须 < 1(否则无空位)
删除直接摘链需要墓碑标记,否则断链
缓存差(节点分散)好(连续探测)
代表std::unordered_map(libstdc++ 桶 + 节点)Java HashMap 早期、Python dict
  • std::unordered_map 的节点在 rehash 时不移动,所以引用 / 指针稳定,迭代器失效——这是高频细节。

实现见 07_哈希表.cpp。

2. 装载因子与 rehash ​

Q: 什么是装载因子?rehash 时迭代器和引用会怎样?

  • 装载因子 = 元素数 / 桶数。太高冲突多,太低浪费内存;
  • 超过阈值触发 rehash:桶数扩到约 2 倍并选下一个质数,重新计算所有元素位置,单次 O(n)。
  • rehash 后所有迭代器失效,但指向元素的引用 / 指针仍然有效(节点本身没搬家)。
  • 已知规模时先 reserve(n),可以避免多次 rehash。

3. unordered_map vs map ​

Q: map 和 unordered_map 有什么区别?怎么选?(高频)

维度mapunordered_map
底层红黑树哈希桶 + 节点
查找 / 插入 / 删除O(log n)平均 O(1),最坏 O(n)
是否有序按 key 有序无序
迭代器稳定性除被删元素外稳定rehash 后全部失效
引用稳定性稳定稳定
内存每节点额外指针 + 颜色桶数组 + 节点,通常更大
适用需要排序、范围、前驱后继纯查找、去重、计数

追问点:

  • map 的 key 是 const,不能直接改——改了会破坏树的有序性。C++17 可用 extract 取出节点句柄,改 key 后再 insert,避免重新分配。
  • operator[] 在 key 不存在时会插入默认值;只想查询用 find / at,at 越界抛 std::out_of_range。
  • unordered_map 最坏 O(n) 来自恶意构造的哈希冲突;需要防攻击时换自定义哈希或改用 map。

4. 位图 ​

底层结构: 由连续的内存空间(通常是数组)构成,数组的每个元素是基本整数类型

核心思想: 用**1个比特(bit)**来标记某个元素的状态(0或1,存在或不存在)

  • 内存映射: 假设用 int(32位)数组存储,数组的一个元素 arr[i] 就可以表示 32 个状态。

    • 第 k 个元素在数组中的位置:arr[k / 32]
    • 它在该元素内部的第几位:k % 32
  • 读写(查/插/删):通过位运算(如 | 置 1,& ~ 置 0)操作,时间复杂度均为 O(1)。

  • 空间消耗极小;但只能记录状态,且如果数据极其稀疏(比如只有1和10000000),会浪费大量空间。

Q: 40 亿个整数去重,内存只有 1GB,怎么做?

用位图:每个数用 1 bit 表示「出现过」,40 亿 × 1 bit = 512MB,可以放下,遍历一遍即可完成去重。

实现见 22_位图.cpp。

5. 布隆过滤器 ​

Q: 布隆过滤器的原理是什么?为什么有假阳性没有假阴性?

  • 用 m 个 bit、k 个独立哈希函数;插入时把 k 个位置置 1,查询时 k 个位置全为 1 才可能存在。
  • 没有假阴性:插入过的元素对应位一定被置 1。
  • 有假阳性:别的元素可能恰好把这 k 位置 1;误判率随元素增多而上升。
  • 不支持删除(会把别人的位清掉);需要删除时用计数布隆过滤器。

工程用途:Redis缓存穿透(先挡掉一定不存在的 key)、URL 去重、数据库避免无效磁盘查询。

实现见 21_布隆过滤器.cpp。

6. 海量数据题 ​

Q: 上亿数据放不进内存,怎么统计 / 去重 / TopK?

四步框架:

  1. 估算内存:数据量 × 单条大小 vs 可用内存。
  2. hash 分流:按 key 哈希到多个小文件,保证相同 key 落在同一文件。
  3. 单机处理:每个小文件用哈希表 / 位图 / 堆独立处理。
  4. 合并结果:小文件的结果再汇总(TopK 用小顶堆)。
题目方案
40 亿 QQ 号去重位图(值域允许时);否则 hash 分流 + 哈希表
100 亿个整数找 TopKhash 分流 → 每片维护大小为 K 的小顶堆 → 合并
两个大文件求共同 URLhash 分流,同 key 同文件,再逐片求交集
出现次数最多的 IPhash 分流 + unordered_map 计数,各片取最大再合并
判断 URL 是否在 100 亿集合中布隆过滤器(允许假阳性)
海量数据全排序外部排序:分块排序 + 多路归并

关键:不要试图一次装进内存;同 key 必须同分片,否则无法局部聚合。

(因为比如7这个数字,出现4次,但被分散了,那就无法统计出4次了)


四、树 ​

1. 二叉树遍历 ​

Q: 前序、中序、后序、层序遍历的递归和迭代写法?

  • 递归:访问语句放在不同位置,就是不同遍历。
  • 前序迭代:栈先压右再压左,弹出即访问。
  • 中序迭代:一路向左入栈,弹栈访问,再转向右子树。
  • 后序迭代:按「根 → 右 → 左」遍历再整体反转;或用两个栈。
  • 层序:队列 + 每层先记录 size,一次处理一层。
cpp
// 中序迭代:左 → 根 → 右
vector<int> inorder(TreeNode* root) {
    vector<int> res;
    stack<TreeNode*> st;
    TreeNode* cur = root;
    while (cur || !st.empty()) {
        while (cur)
        {
            st.push(cur);
            cur = cur->left;
        }
        cur = st.top();
        st.pop();
        res.push_back(cur->val);
        cur = cur->right;
    }
    return res;
}
  • 时间 O(n);递归栈 O(h),层序队列 O(w),h 为树高、w 为最大宽度。
  • 易错点:后序不能简单「根右左」直接输出,必须反转;中序迭代的 cur = cur->right 在访问之后。

实现见 09_二叉树遍历.cpp。

2. BST 二叉搜索树 ​

Q: 二叉搜索树的增删查怎么做?删除节点有哪几种情况?

  • 性质:左子树全部小于根,右子树全部大于根;中序遍历有序。
  • 删除分三种:
    1. 叶子:直接删。
    2. 只有一个孩子:孩子顶替。
    3. 两个孩子:用中序后继(右子树最小值)或前驱替换值,再删除后继节点。
  • 查找 / 插入 / 删除平均 O(log n),最坏 O(n)——按有序序列插入会退化成链表。

高频追问:

  • 验证 BST 不能只比较父子,要传上下界:左子树 < root 且 > lower,右子树 > root 且 < upper。
  • 第 k 小:中序遍历计数。
  • BST 的最近公共祖先:从根开始,两个值都小于根就往左,都大于就往右,否则当前就是 LCA。
  • 插入顺序决定树高;工程上需要平衡,才有 AVL / 红黑树。

实现见 10_二叉搜索树.cpp。

4. AVL 树 ​

BST(二叉搜索树)和 AVL 树的区别一句话:AVL 树是一棵“会自己保持平衡”的 BST。

Q: AVL 树怎么保持平衡?四种旋转分别对应什么情况?

平衡因子 = 左子树高 - 右子树高,取值只能是 -1 / 0 / 1,否则旋转。

失衡类型场景处理
LL左孩子的左子树过高对节点右旋一次
RR右孩子的右子树过高对节点左旋一次
LR左孩子的右子树过高先对左孩子左旋,再对节点右旋
RL右孩子的左子树过高先对右孩子右旋,再对节点左旋
  • 查找、插入、删除都 O(log n),树高严格 O(log n)。
  • 比红黑树更「矮胖」,查找更快;但插入 / 删除要维护严格平衡,旋转更多。
  • 适合读多写少的场景;std::map 选择的是红黑树,不是 AVL。

实现见 11_AVL树.cpp。

5. 红黑树 ​

Q: 红黑树的性质是什么?为什么 map 和 epoll 都用红黑树,而不用 AVL?

五条性质:

  1. 每个节点非红即黑。
  2. 根节点是黑色。
  3. 叶子(NIL)是黑色。
  4. 红节点的两个孩子必须是黑色(不能有连续红节点)。
  5. 从任一节点到其所有叶子的路径上,黑节点数量相同。

由性质 4、5 可推出:最长路径不超过最短路径的 2 倍,树高 ≤ 2 log₂(n+1),所以增删查都是 O(log n)。

维度AVL红黑树
平衡程度严格(高度差 ≤ 1)宽松(黑高平衡)
查找略快略慢
插入 / 删除旋转多旋转少、重着色多
适用读多写少读写混合、通用
  • std::map/set、Linux epoll 的 fd 管理、CFS 调度器都用红黑树:要有序、要 O(log n) 最坏保证、写操作不能太贵。
  • 不用哈希:需要范围查询 / 前驱后继;不用 AVL:写操作旋转太频繁。

6. B 树与 B+ 树 ​

Q: 为什么数据库索引用 B+ 树,不用红黑树或哈希?(高频)

维度红黑树B 树B+ 树
分叉二叉多叉多叉
数据位置所有节点所有节点只在叶子,内部节点只存 key
叶子链表无无有,支持范围扫描
树高(百万级)~20~3~3
磁盘 I/O每层一次随机 I/O少更少

核心原因是磁盘:B+ 树一个节点就是一页(InnoDB 默认 16KB),扇出可达上千,百万数据只需 3~4 层,也就是 3~4 次 I/O;红黑树 20 层就是 20 次随机 I/O。

  • B+ 树 vs B 树:内部节点不存数据 → 同样一页能放更多 key → 扇出更大、树更矮;叶子有链表 → 范围查询、排序、分页友好;所有查询都走到叶子,性能稳定。
  • 为什么不用哈希:哈希只能等值查询,无法范围查询、排序、最左前缀匹配。
  • InnoDB:聚簇索引的叶子存整行;二级索引的叶子存主键,查非索引列要回表;覆盖索引可以避免回表。

7. 堆 ​

Q: 堆的底层为什么用数组?建堆为什么是 O(n) 而不是 O(n log n)?

堆是完全二叉树,可以按层序存进数组,不需要指针:

text
parent(i) = (i - 1) / 2
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2
  • 插入:放到数组末尾,然后上浮,O(log n)。
  • 删除堆顶:堆顶与末尾交换,弹出末尾,再对堆顶下沉,O(log n)。
  • 建堆:从最后一个非叶子节点 n/2 - 1 开始向前下沉。总代价是各节点高度之和,约 2n,所以 O(n)。
  • 堆排序:建堆 O(n) + n 次取堆顶 O(n log n),原地、不稳定。

priority_queue:底层 vector + make_heap / push_heap / pop_heap;默认大顶堆

小顶堆写 priority_queue<int, vector<int>, greater<int>>;

不支持迭代器遍历,也不支持修改堆中任意元素。

实现见 08_二叉堆.cpp、18_堆排序.cpp。

8. TopK 与对顶堆 ​

Q: 海量数据取 TopK 有哪几种做法?数据流的中位数怎么维护?

方法时间空间适用
排序后取前 kO(n log n)O(n)数据量小
大小为 k 的小顶堆O(n log k)O(k)流式 / 海量数据
快速选择 quickselect平均 O(n),最坏 O(n²)O(1)允许打乱数组、一次性
分治 + 每片堆O(n log k)O(k × 分片)单机内存放不下
  • 第 k 大:维护小顶堆,堆顶就是当前第 k 大;比堆顶大才替换。
  • 数据流中位数:左边大顶堆存较小一半,右边小顶堆存较大一半;保持两堆大小差 ≤ 1,中位数取堆顶。
  • 合并 K 个有序链表:小顶堆存每个链表当前节点,O(N log k)。

实现见 08_二叉堆.cpp、26_合并K个有序链表.cpp。

9. Trie(前缀树/字典树) ​

Q: Trie 的结构和复杂度?适合什么场景?

  • 每个节点代表一个字符,从根到某节点的路径是一个前缀;节点用 end 标记是否为完整单词。
  • 插入 / 查询 / 前缀判断都是 O(L),L 为字符串长度,与集合大小无关。
  • 代价是内存:每个节点若开 26 个指针就很重;可用 unordered_map<char, Node*> 或压缩成基数树 / 压缩 Trie。
  • 场景:自动补全、敏感词过滤、IP 路由前缀匹配、拼写检查、词频统计。

实现见 12_前缀树.cpp。

10. 跳表 ​

Q: 跳表的原理是什么?Redis 为什么用跳表而不是红黑树?

  • 在有序链表上建多层索引,每层以概率 p(Redis 取 1/4)向上晋升;查找从最高层开始,逐层下降。
  • 期望时间 O(log n),最坏 O(n)(随机性导致);空间期望 O(n)。
  • 相比红黑树:实现简单、范围查询天然友好、并发加锁粒度小;代价是随机性和额外指针内存。
  • Redis zset 同时用跳表 + 哈希表:哈希负责 O(1) 查 score,跳表负责按 score 排序和范围查询(ZRANGE)。

实现见 23_跳表.cpp。


五、排序与查找 ​

2. 快速排序 ​

Q: 快排的原理、最坏情况、如何优化?

  • 选 pivot,partition 把小的放左、大的放右,再递归两侧。
  • 最坏 O(n²):数组已经有序且总选第一个 / 最后一个元素做 pivot,每次划分极不平衡。
  • 优化:
    1. 随机 pivot 或三数取中,避免有序输入退化。
    2. 小区间(如 < 16)改用插入排序,减少递归开销。
    3. 先递归较小的一侧,较大的一侧尾递归 / 迭代,栈深控制在 O(log n)。
    4. 大量重复元素用三路划分(小于 / 等于 / 大于),避免全相等时退化。
  • 平均 O(n log n),原地、不稳定;实际最快是因为内存连续、常数小、缓存友好。

实现见 16_快速排序.cpp。

3. 归并排序 ​

Q: 归并排序的特点?为什么链表排序适合归并?

  • 分治:递归排序两半,再线性合并两个有序数组。
  • 时间稳定 O(n log n),稳定,空间 O(n)。
  • 链表:合并只需改指针,不需要额外数组,可以做到 O(1) 额外空间;快排对链表不友好(无法随机访问)。
  • 求逆序对:合并时若 a[i] > a[j],则 a[i..mid] 都大于 a[j],一次贡献 mid - i + 1 个逆序对。
  • 外部排序的基础:内存里排好块,再多路归并。

实现见 17_归并排序.cpp。

4. 堆排序 ​

Q: 堆排序的过程和优缺点?

  1. 建堆 O(n)。
  2. 每次把堆顶与末尾交换,堆大小减一,再下沉,重复 n 次。
  • 时间 O(n log n),空间 O(1),不稳定。
  • 优点是最坏也有 O(n log n) 且原地;缺点是缓存不友好(跳跃访问),实际通常慢于快排。
  • std::sort 在快排递归过深时会切换到堆排兜底,就是为了这个最坏保证。

实现见 18_堆排序.cpp。

5. std::sort 的内省排序 ​

Q: std::sort 用的是什么算法?为什么它不稳定还能这么快?

std::sort 用内省排序(introsort):

  1. 主体是快排;
  2. 递归深度超过 2 log n 时切换成堆排,保证最坏 O(n log n);
  3. 小区间切换成插入排序。
  • 三者结合:快排的平均速度 + 堆排的最坏保证 + 插入排序的小数组低开销。
  • 不稳定;需要稳定排序用 std::stable_sort(归并,尽量复用缓冲区)。
  • std::partial_sort 用堆;std::nth_element 用快速选择。

6. 外部排序 ​

Q: 数据量大于内存时怎么排序?

  1. 分块:每次读入能放进内存的一块,内部排序后写回磁盘,形成若干有序「归并段」。
  2. 多路归并:用大小为 k 的小顶堆合并 k 个有序段,边读边写。
  3. 重复直到只剩一个有序文件。

六、图 ​

1. 图的存储 ​

Q: 邻接矩阵和邻接表怎么选?

邻接矩阵邻接表
空间O(V²)O(V + E)
判断边是否存在O(1)O(度数)
遍历某点邻居O(V)O(度数)
适合稠密图、Floyd稀疏图、大多数题
  • 无向图一条边要存两次;带权图在边上加 w。
  • 笔试也常用链式前向星(数组模拟邻接表):head[u] + next + to + w,避免大量 new,缓存更友好。

2. BFS / DFS ​

Q: BFS 和 DFS 分别适合什么?复杂度多少?

BFSDFS
数据结构队列递归栈 / 显式栈
特点按层扩展,无权图最短路一条路走到黑,适合连通性 / 路径 / 环
空间O(V)(最坏一层)O(h)(递归深度)
复杂度O(V + E)O(V + E)
  • 网格题(岛屿数量、腐烂的橘子、迷宫)把每个格子看成节点,上下左右是边。
  • 易错点:BFS 应在入队时标记 visited,否则同一节点会被重复入队,复杂度退化。
  • 无权图最短路用 BFS;带权图才用 Dijkstra。

3. 拓扑排序 ​

Q: 拓扑排序的两种写法?如何判断有环?有什么用?

只适用于有向无环图(DAG)。

  • Kahn(BFS):统计入度,入度为 0 的入队;每次弹出一个、把它指向的节点入度减 1;若最终输出的节点数 < n,说明有环。
  • DFS:三色标记(0 未访问 / 1 访问中 / 2 已完成);遇到「访问中」的节点说明有环;后序结果的逆序就是拓扑序。
  • 应用:课程表、编译依赖、任务调度、包管理器的依赖解析。

实现见 14_拓扑排序.cpp。

4. Dijkstra ​

Q: Dijkstra 的原理?为什么不能处理负权边?复杂度多少?

  • 贪心:每次从「未确定」的节点中取 dist 最小的,它的最短路已经确定,然后用它去松弛邻居。
  • 用 priority_queue<pair<dist, node>, ..., greater<>>,弹出时若 d > dist[u] 就跳过(惰性删除,代替 decrease-key)。
  • 复杂度 O((V + E) log V),适合非负权。
  • 负权边会破坏贪心前提:已经「确定」的节点之后可能被一条负边改小,所以 Dijkstra 不成立;负权用 Bellman-Ford / SPFA。

实现见 15_Dijkstra最短路.cpp。

5. Bellman-Ford / SPFA / Floyd ​

Q: 负权最短路和全源最短路分别用什么算法?

算法负权边负环检测复杂度适用
Bellman-Ford支持支持O(VE)单源、有负权
SPFA支持支持平均较快,最坏 O(VE)单源、稀疏图(竞赛常用)
Floyd支持支持(对角线 < 0)O(V³)全源、小图
  • Bellman-Ford:对所有边松弛 V-1 轮;第 V 轮还能松弛,说明存在负环。
  • SPFA:只把被松弛过的节点入队,是 Bellman-Ford 的队列优化;最坏仍会退化,出题人可构造数据卡它。
  • Floyd:dp[k][i][j] 表示只允许经过前 k 个点的最短路,三重循环;代码短,适合 V ≤ 500。

6. 最小生成树 ​

Q: Prim 和 Kruskal 有什么区别?分别适合什么图?

PrimKruskal
思路从一个点开始,每次加一条连接「已选 / 未选」的最短边所有边排序,依次加入不成环的边
数据结构优先队列并查集
复杂度O(E log V)O(E log E)
适合稠密图稀疏图
  • 正确性都来自切分性质:横跨任意切分的最小边一定属于某棵 MST。
  • Kruskal 判环用并查集:两端已连通就跳过。

7. 并查集 ​

Q: 并查集怎么实现?为什么近似 O(1)?

  • parent[x] 指向父节点;根节点 parent[x] == x。
  • 路径压缩:查找时把路径上的节点直接挂到根上。
  • 按秩 / 按大小合并:矮树挂到高树下,避免退化成链。
  • 两者结合后,单次操作的摊还复杂度是 O(α(n)),α 是反阿克曼函数,实际可视为常数。

应用:连通分量、Kruskal、冗余连接、账户合并、等式方程可满足性、岛屿数量(也可 DFS)。

cpp
int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];   // 路径减半
        x = parent[x];
    }
    return x;
}

实现见 13_并查集.cpp。


七、设计题与并发结构 ​

1. LRU Cache (Least Recently Used 最近最少使用缓存淘汰算法) ​

最近被访问过的数据,未来更可能再次被访问;很久没被访问的数据,未来不太可能被访问。

Q: 设计一个 O(1) 的 LRU,为什么必须是「哈希表 + 双向链表」?(高频)

  • 哈希表:O(1) 查找数据:get哈希定位节点,把它移到链表头(最近使用)。
  • 双向链表:O(1) 把访问过的节点put移到链表头,淘汰时删除链表尾(最久未使用)。
  • 为什么不用单链表:删除尾部需要前驱,双向链表才能 O(1)。
  • 为什么不用数组:中间移动 / 删除 O(n)。
  • 为什么不用 map:map 是 O(log n),哈希才能 O(1)。

并发追问:全局加锁简单竞争大;分片(sharded LRU)把 key 哈希到多个独立 LRU,各自加锁,是工程常见做法。

实现见 03_LRU缓存.cpp。

2. LFU Cache (Least Frequently Used Cache 最不经常使用缓存) ​

当缓存满了,优先淘汰访问频率最低的数据;如果频率相同,通常再按 LRU(最久未使用) 淘汰。

Q: LFU 怎么做到 O(1)?和 LRU 有什么区别?

  • 哈希表 key -> node:快速定位缓存节点
  • 哈希表 freq -> 双向链表:每个频率对应一个链表,链表内按 LRU 排序
  • 维护一个 minFreq:记录当前最小频率,淘汰时从 minFreq 对应链表尾部删除
  • 节点通常保存:key, value, freq

操作逻辑:

  • Get(key):不存在返回 -1;存在则频率 +1,并移动到新频率链表的头部
  • Put(key, value):
    • key 存在:更新 value,频率 +1
    • key 不存在:若容量满,删除 minFreq 链表尾部节点;插入新节点,频率为 1,并更新 minFreq = 1
LRULFU
淘汰依据最久未使用使用频率最低(同频再按 LRU)
优点实现简单,适应访问模式变化保护高频热点
缺点偶发批量访问会冲刷热点历史频率僵化,新热点难上位

LFU 的工程问题:频率只增不减,旧热点会一直占位;常见解法是定期衰减频率。

实现见 04_LFU缓存.cpp。

3. 最小栈 ​

在普通栈的基础上,额外支持 O(1) 时间复杂度获取当前栈中的最小值。

普通栈支持:

  • push(x):入栈
  • pop():出栈
  • top():看栈顶
  • empty():是否为空

最小栈还要支持:

  • getMin():返回当前栈中最小元素

Q: 如何让 push / pop / top / getMin 都是 O(1)?

用两个栈:

  • dataStack:存所有数据
  • minStack:存当前对应的最小值

规则:

  • push(x):
    • dataStack 入栈 x
    • minStack 入栈 min(x, 当前最小值)
  • pop():
    • 两个栈同时弹出
  • top():返回 dataStack 栈顶
  • getMin():返回 minStack 栈顶

实现见 05_最小栈.cpp。

4. 两个栈实现队列 ​

Q: 两个栈怎么实现队列?复杂度怎么分析?

  • in 栈负责入队,out 栈负责出队。
  • 出队时若 out 为空,把 in 全部倒入 out,顺序正好反过来。
  • 摊还 O(1):每个元素最多被倒入一次、弹出一次;但单次 pop 最坏 O(n)(倒栈那一次)。
  • 反过来「两个队列实现栈」:每次 push 后把队列前面的元素转到后面,或者用两个队列来回倒。

实现见 06_双栈队列.cpp。

5. O(1) 随机插入 / 删除 ​

Q: 设计一个支持 O(1) 插入、删除、随机取元素的结构。

vector + unordered_map<value, index>:

  • 插入:追加到 vector 尾部,记录下标。

  • 删除:把待删元素与末尾元素交换,pop_back,更新被交换元素的下标。

  • 随机取:nums[rand() % nums.size()]。

  • 「swap-remove」是数组 O(1) 删除的通用技巧。

  • 有重复元素时哈希要存 value -> set<index>,或者改用计数。

实现见 25_随机集合.cpp。

6. 合并 K 个有序链表 ​

Q: 合并 K 个有序链表有哪几种做法?

  • 小顶堆:每个链表当前节点入堆,每次取最小,再把它的 next 入堆;O(N log k),N 为总节点数。
  • 分治归并:两两合并,O(N log k),常数更小、不需要堆。
  • 朴素做法每次比较 k 个头节点是 O(Nk),不可取。

实现见 26_合并K个有序链表.cpp。

7. 线程安全队列 ​

Q: 有界阻塞队列怎么实现?为什么 wait 必须带谓词?

  • mutex + 两个 condition_variable(非空 / 非满)+ 有界 queue。
  • push:队列满则等待「非满」;入队后 notify_one 唤醒消费者。
  • pop:队列空则等待「非空」;出队后 notify_one 唤醒生产者。
  • wait(lock, predicate) 必须带谓词:条件变量存在虚假唤醒,醒来看谓词不成立要继续等。
  • 执行任务时绝不能持锁,否则线程池退化成串行。

实现见 27_线程安全队列.cpp;线程池就是「生产者-消费者 + 线程复用」:提交任务加锁入队,工作线程 wait 取任务,执行时释放锁。

8. 无锁队列与 ABA ​

Q: 无锁队列怎么实现?ABA 问题是什么?

  • SPSC:见 §二.7,单生产者单消费者只需两个原子下标 + acquire/release。
  • MPMC:多生产者多消费者要用 CAS 循环(如 Michael-Scott 队列),复杂度高很多。
  • ABA:线程读到值 A,准备 CAS 时值被改成 B 又改回 A,CAS 误以为没变。解法:带版本号的 tagged pointer、 hazard pointer。
  • 选型:无锁适合临界区极短、竞争极高的场景;一般业务用互斥锁更简单可靠。

内存序只需记住:自己写的下标用 relaxed,发布数据用 release,读取对方下标用 acquire;CAS 的 ABA 用版本号或 hazard pointer 解决。

9. 定时器最小堆(项目常问) ​

Q: 网络库的定时器为什么常用最小堆?

  • 定时器需要频繁「插入超时任务」和「取最早到期任务」:堆的插入 O(log n)、取最小 O(1),正好匹配。
  • 取消定时器可用惰性删除:标记取消,等它到堆顶时再丢弃,避免在堆中查找 O(n)。
  • 对比:有序链表插入 O(n);红黑树插入 O(log n) 但常数更大、实现复杂;时间轮适合大量定时器、精度要求不极端的场景。
  • 工程组合:timerfd 负责「什么时候醒」,最小堆负责「下一个该处理谁」。

典型组合:epoll 负责监听 fd 事件,timerfd 负责报时,最小堆负责选出下一个到期连接。