第八章 问题与解答 (Problems and Solutions)
一、导读
1.1 本章学习目标
通过综合性的问题来巩固和运用前七章学到的算法设计技术
学会将复杂问题分解为多个子问题，并选择适当的技术来解决每个子问题
掌握在实际约束条件下（时间、空间、正确性）设计解决方案的方法
培养从多个角度审视问题、寻找最优解的思维能力
学会在解决方案的优雅性和实用性之间做出合理的权衡
通过分析和讨论他人的解决方案来拓展自己的算法设计视野
理解算法设计中"trade-off"（权衡）的普遍性和重要性
1.2 为什么本章如此重要
本章是全书的总结和实践环节。Bentley 精心挑选了一系列综合性问题，每个问题都需要综合运用前几章介绍的多种技术来解决。这些问题涵盖了排序、搜索、数据结构选择、算法优化、系统思维等多个方面，是对前面所学知识的全面检验。
通过解决这些综合性问题，读者可以将零散的知识点串联起来，形成完整的算法设计能力。每个问题都没有唯一的标准答案——不同的约束条件和优先级会导致不同的最优解。这种开放性正是实际软件工程的特征：在现实中，问题往往是模糊的，约束条件是多样的，需要在多个目标之间做出权衡。
本章还强调了"问题定义"的重要性。许多时候，解决问题的第一步是正确地定义问题：明确输入和输出、理解约束条件、确定优化目标。一个正确定义的问题已经解决了一半。Bentley 通过多个例子展示了如何从模糊的需求中提炼出清晰的算法问题。
对于准备技术面试的读者来说，本章的问题也是极好的练习材料。它们涵盖了面试中最常见的算法主题，同时要求候选人展示分析问题和解决问题的能力，而不仅仅是记忆算法模板。
1.3 核心问题引导
如何在一个有 10 亿个整数的文件中找到第 K 大的整数？内存只有 1 GB 怎么办？
如何设计一个高效的拼写检查器？
给定一组城市之间的距离，如何找到最短的旅行路线（旅行商问题的近似解）？
如何设计一个支持快速插入、删除和随机选择的集合数据结构？
如何在有限的内存中对超大规模数据进行排序？
如何设计一个高效的 LRU 缓存？
二、核心概念详解
2.1 选择问题的多种解法
选择问题（Selection Problem）——在一组数据中找到第 K 大（或第 K 小）的元素——是综合性问题的经典代表。这个问题有多种解法，每种解法展示了不同的算法技术。
最直接的解法是排序后取第 K 个元素，时间复杂度 O(n log n)。但这不是最优的——快速选择算法（Quickselect）可以在平均 O(n) 的时间内解决选择问题。它的思想类似于快速排序：随机选择一个主元，将数组分为两部分，然后只在包含第 K 个元素的那一半继续递归。
如果数据量大到无法全部放入内存，可以使用外部选择算法：将数据分成多个块，每块排序后写回磁盘，然后通过多路归并来找到第 K 个元素。另一种方法是使用计数排序的思想：如果数据范围有限，可以统计每个值出现的次数，然后从大到小（或从小到大）累加计数，直到达到 K。
如果内存极其有限（只有几百字节），可以使用随机采样来近似：随机抽取一个样本，排序后取第 K' 个元素作为近似答案。虽然不精确，但在许多实际场景中可以接受。
2.2 搜索问题的综合应用
搜索问题的综合性体现在需要结合多种数据结构和技术来满足不同的查询需求。一个典型的案例是设计一个地理信息系统（GIS），需要支持以下查询：按名称查找城市、按坐标查找最近的城市、查找给定区域内的所有城市、按人口排序城市。
每种查询需要不同的数据结构：按名称查找适合使用哈希表或搜索树；最近邻查询适合使用 KD 树或四叉树；区域查询适合使用 R 树或网格索引；排序查询需要维护有序结构。
设计这样一个系统的关键挑战是：如何在有限的内存中同时支持多种查询。一种方案是为每种查询维护一个独立的数据结构，代价是内存消耗较大。另一种方案是使用一种主数据结构（如搜索树），其他查询通过遍历主数据结构来实现，代价是查询速度较慢。实际的设计需要在内存和速度之间做出权衡。
2.3 字符串处理的综合技术
字符串处理是另一个综合性很强的领域。一个典型的综合问题是设计一个文本搜索引擎：给定一组文档，支持关键词搜索、短语搜索和布尔查询。
关键词搜索可以使用倒排索引：对每个词，记录它出现在哪些文档中。查询时，取出关键词对应的文档列表即可。短语搜索需要记录词的位置信息：对每个词，不仅记录文档 ID，还记录在文档中的位置。查询短语时，检查各个词的位置是否连续。
布尔查询（AND、OR、NOT）需要对文档列表进行集合运算：AND 对应交集，OR 对应并集，NOT 对应差集。如果文档列表是有序的，交集和并集可以在 O(m + n) 时间内完成。
更高级的搜索功能（如模糊搜索、相关性排序）需要引入更多的技术：编辑距离用于模糊匹配，TF-IDF 用于相关性评分，PageRank 用于重要性排序。
2.4 随机化算法
随机化算法（Randomized Algorithm）是在算法中引入随机性的技术。它虽然不能保证每次都得到正确的结果或最优的解，但在期望意义下有很好的性能保证。
快速排序的随机化版本通过随机选择主元来避免最坏情况。虽然最坏情况仍然是 O(n²)，但最坏情况的概率极低（约为 1/2^n），期望时间复杂度为 O(n log n)。
随机化选择算法（Randomized Selection）通过随机选择主元来在平均 O(n) 时间内找到第 K 个元素。与确定性算法（如 Median of Medians）相比，随机化算法的常数因子更小，实践中更快。
随机化在哈希表中也有重要应用：通用哈希（Universal Hashing）通过从一族哈希函数中随机选择来避免对手构造最坏情况的输入。
2.5 近似算法
许多实际问题（如旅行商问题、集合覆盖问题）是 NP 难的，不存在已知的多项式时间精确算法。在这种情况下，近似算法（Approximation Algorithm）提供了一个实用的替代方案：在多项式时间内找到一个"足够好"的解。
旅行商问题（TSP）的最近邻近似算法：从任意城市出发，每次选择最近的未访问城市，最后返回起点。这个算法的时间复杂度为 O(n²)，解的长度不超过最优解的 O(log n) 倍。对于度量空间中的 TSP（满足三角不等式），Christofides 算法可以保证解的长度不超过最优解的 1.5 倍。
集合覆盖问题的贪心近似算法：每次选择能覆盖最多未覆盖元素的集合。这个算法的近似比为 O(log n)，即解的大小不超过最优解的 O(log n) 倍。
近似算法的设计需要在解的质量和计算时间之间做出权衡。更好的近似比通常需要更复杂的算法和更长的运行时间。
三、深入分析与讨论
3.1 问题的重新定义
Bentley 反复强调的一个重要技巧是：在面对一个困难的问题时，尝试重新定义问题。有时候，一个看似困难的问题，在重新定义后可以变得简单得多。
例如，"在文本中找到最长的重复子串"这个问题，如果直接解决需要复杂的动态规划（O(n²) 时间）。但如果将问题重新定义为"在排序后的后缀数组中找到最长的公共前缀"，则可以通过排序 + 线性扫描在 O(n log n) 时间内解决。
另一个例子是"检测链表是否有环"。直接追踪访问过的节点需要 O(n) 的额外空间。Floyd 的"龟兔赛跑"算法通过两个不同速度的指针来检测环，只需要 O(1) 的额外空间。这个算法的精妙之处在于将"检测环"的问题转化为"两个指针是否会相遇"的问题。
3.2 多种技术的组合
综合性问题的解决通常需要组合多种技术。例如，设计一个高效的缓存系统需要：哈希表（快速查找）、双向链表（维护访问顺序）、并发控制（多线程安全）。每种技术解决一个子问题，组合起来形成完整的解决方案。
LRU 缓存就是一个经典案例：使用哈希表实现 O(1) 的查找，使用双向链表维护访问顺序（最近访问的放在头部，最久未访问的在尾部）。当缓存满时，删除尾部元素。当访问一个元素时，将其移到头部。所有操作都是 O(1) 时间。
3.3 空间-时间-开发时间的三维权衡
在实际工程中，设计决策通常需要在三个维度上进行权衡：运行时间、空间消耗和开发时间。一个算法可能运行很快但需要大量内存；另一个算法可能节省内存但运行较慢；第三个算法可能两者都适中但实现复杂。
最优的选择取决于具体的约束条件。在实时系统中，运行时间是最重要的约束；在嵌入式系统中，内存可能是最紧缺的资源；在快速原型开发中，开发时间可能是最关键的瓶颈。优秀的工程师能够根据具体的约束条件，做出合理的权衡决策。
四、实践案例
4.1 设计一个 URL 短链接服务
一个综合性的系统设计问题：设计类似 bit.ly 的 URL 短链接服务。需要支持：将长 URL 转换为短 URL、将短 URL 还原为长 URL、处理高并发的访问。
核心算法是将长 URL 映射为短码。一种方法是使用自增 ID 的 Base62 编码（0-9, a-z, A-Z）：第一个短链接是 0，第二个是 1，第 62 个是 Z，第 63 个是 10。6 位 Base62 编码可以表示 62⁶ ≈ 568 亿个短链接，足够使用。
存储层使用键值数据库（如 Redis），以短码为键、长 URL 为值。为了实现高并发，可以使用分布式缓存和数据库分片。通过一致性哈希将请求分散到多个服务器上。
4.2 海量数据中的 Top K 问题
在 100 亿个整数中找到最大的 1000 个。数据量大到无法全部放入内存。
方案一：维护一个大小为 1000 的最小堆。逐个读入整数，如果大于堆顶元素，就替换堆顶并调整堆。最终堆中的 1000 个元素就是最大的 1000 个。时间复杂度 O(n log K)，空间复杂度 O(K)。
方案二：使用快速选择的变体。随机采样一部分数据，找到一个合适的阈值，将数据分为"大于阈值"和"小于阈值"两部分。如果"大于阈值"的部分恰好约 1000 个，就在这个部分中精确排序；如果太多或太少，调整阈值重新划分。
五、常见误区与注意事项
5.1 追求完美解而忽视实用解
在许多情况下，最优解的计算成本过高，而一个"足够好"的近似解可以在很短的时间内获得。工程师应该学会在解的质量和计算成本之间做出合理的权衡。
5.2 忽视问题的约束条件
同一个问题在不同的约束条件下可能有完全不同的最优解。在开始解决问题之前，必须明确所有的约束条件：数据规模、内存限制、时间要求、是否需要精确解等。
5.3 不验证解决方案的正确性
在解决复杂问题时，容易引入边界条件的错误。应该通过小规模的手工测试、边界值测试和随机测试来验证解决方案的正确性。
5.4 不考虑解决方案的可维护性
一个巧妙但晦涩的算法可能比一个简单但稍慢的算法更难维护。在选择解决方案时，应该考虑团队的维护能力和代码的长期演进需求。
六、本章小结
本章通过一系列综合性问题，展示了如何将前几章学到的算法设计技术综合运用来解决实际问题。选择问题、搜索问题、字符串处理、随机化算法和近似算法都是重要的综合性主题。问题的重新定义是解决困难问题的关键技巧——通过变换视角，可以将复杂问题转化为简单问题。多种技术的组合是解决综合性问题的基本方法。最终，工程设计需要在空间、时间和开发成本之间做出合理的权衡。
七、思考题与练习
设计一个算法，在 10 亿个整数中找到中位数，内存限制为 100 MB。
实现一个 LRU 缓存，支持 O(1) 的 get 和 put 操作。
设计一个拼写检查器，支持模糊匹配（允许 1-2 个字符的编辑距离）。
给定一个大型文本文件，设计一个算法找到出现频率最高的 10 个单词。
实现一个支持以下操作的数据结构：insert(x) O(log n)、delete(x) O(log n)、getRandom() O(1)。
设计一个算法来检测一个链表中是否存在环。如果存在环，找到环的起始节点。要求 O(n) 时间和 O(1) 空间。
设计一个 URL 短链接服务，支持每天 1 亿次短链生成和 10 亿次访问。
给定一组矩形（每个矩形由宽度和高度定义），设计一个算法找到可以嵌套的最大矩形链（矩形 A 可以嵌套在矩形 B 中，当且仅当 A 的宽度和高度都小于 B）。