1. 从“谦虚数字”到“丑数”一个经典算法的变体与实战最近在准备蓝桥杯这类算法竞赛的同学可能都刷到过“谦虚数字”这道题。乍一看标题有点摸不着头脑——“谦虚”这个词怎么和数字算法扯上关系了其实这背后是一个在算法竞赛和面试中都非常经典的模型它有一个更广为人知的名字丑数Ugly Number或其变体——超级丑数Super Ugly Number。我第一次遇到这类题目时也卡了很久。题目描述通常是给定一个质数集合或者一个递增的质数序列定义“谦虚数字”为所有质因数都来自这个集合的正整数。要求找出第 n 个这样的“谦虚数字”。这不就是“超级丑数”的定义吗只不过把通常的质因数集合 {2, 3, 5} 扩展到了任意给定的质数集合。理解这个模型不仅能帮你秒杀“谦虚数字”这道题更能让你掌握一类解决“按特定规则生成有序序列”问题的通用思想——多路归并Multi-way Merge。今天我就结合自己刷题和打比赛的经验把这个问题的来龙去脉、核心解法、代码实现细节以及那些容易踩的坑掰开揉碎了讲清楚。2. 问题本质剖析为什么是“多指针”而不是“暴力生成”我们先来明确一下“谦虚数字”到底要我们做什么。假设给定的质数集合是primes [2, 7, 13, 19]那么1 是第一个谦虚数字通常约定虽然1没有质因数但包含在序列中。接下来的数字其质因数只能从{2, 7, 13, 19}中选取。所以 2, 4(22), 7, 8(222), 13, 14(27), 16(222*2), 19... 都是谦虚数字。而像 3, 5, 6(23), 10(25) 等包含集合外质因数的数字则不是。最直观也最错误的想法可能是从1开始遍历每一个自然数判断它是否只由给定质数构成。判断方法是对每个数进行质因数分解检查所有质因数是否都在集合内。这个方法的复杂度是 O(n * sqrt(m))其中 n 是我们要找的第 n 个谦虚数字m 是这个数字的大小。当 n 较大时比如题目常要求的第 1500 个这个数字 m 可能非常大导致分解耗时极长必然超时。那么正确的思路是什么关键在于谦虚数字序列是有序递增的。我们不需要去“检查”一个数是不是而是可以主动“生成”下一个。怎么生成下一个谦虚数字必然是由已有的某个较小的谦虚数字乘以给定质数集合中的某个质数得到的。这就引出了核心的“多路归并”思想我们维护一个结果数组dpdp[0] 1。我们为质数集合primes中的每一个质数p维护一个指针index[p]它指向当前dp数组中的某个位置。这个指针的含义是对于质数 p 来说下一个可能生成的谦虚数字将是dp[index[p]] * p。每一轮我们遍历所有质数计算dp[index[p]] * p找出其中的最小值。这个最小值就是下一个谦虚数字我们把它放入dp数组。然后所有计算得到这个最小值的质数它们的指针index[p]都需要向后移动一位。这是因为对于这些质数 p 来说用当前指针指向的dp值乘以 p 已经生成了最新的谦虚数字下一个可能的最小值就需要用dp中下一个更大的数来乘以 p 了。这个过程就像我们有 k 个k 是质数集合大小有序链表每个链表是dp[i] * p我们需要合并它们并保持整体有序。这就是“多路归并”。为什么这个算法高效它的时间复杂度是 O(n * k)其中 n 是我们要找的序号k 是质数集合的大小。我们只需要进行 n 次循环每次在 k 个候选值中找最小。这比暴力判断每个数快了几个数量级。空间上我们需要 O(n) 来存储dp数组以及 O(k) 来存储指针。3. 核心算法实现与逐行代码解读理解了原理我们来看代码实现。这里以 Python 为例因为它最贴近伪代码易于理解。我会假设质数集合已经按升序给出。def nth_super_ugly_number(n, primes): 返回第n个谦虚数字超级丑数。 :param n: int, 需要的第n个数字的序号从1开始 :param primes: List[int], 质数集合假设已排序且无重复 :return: int # dp[i] 表示第 i1 个谦虚数字因为列表索引从0开始 dp [1] * n # 指针数组长度等于质数集合大小初始都指向dp[0]即1 # pointers[i] 表示对于质数 primes[i]下一个候选值将是 dp[pointers[i]] * primes[i] pointers [0] * len(primes) # 从生成第2个数字开始第1个dp[0]已经是1 for i in range(1, n): # 步骤1找出所有质数路径上的下一个候选值中的最小值 next_candidates [dp[pointers[j]] * primes[j] for j in range(len(primes))] next_val min(next_candidates) dp[i] next_val # 步骤2将所有产生这个最小值的质数的指针后移一位 for j in range(len(primes)): if dp[pointers[j]] * primes[j] next_val: pointers[j] 1 return dp[n-1] # 示例质数集合为 [2, 7, 13, 19]求第10个谦虚数字 primes [2, 7, 13, 19] n 10 result nth_super_ugly_number(n, primes) print(f“第{n}个谦虚数字是{result}”) # 输出应该是 32 (序列1,2,4,7,8,13,14,16,19,26,28,32... 第10个是32我们需要验证)等等我们跑一下逻辑。序列前几个1, 2(12), 4(22), 7(17), 8(42), 13(113), 14(27), 16(82), 19(119), 26(13*2)... 所以第10个是26不是32。我上面的示例计算有误这正好引出了我们需要验证算法正确性的重要性。让我们手动模拟或者用代码正确计算一下。实际上上面的代码逻辑是正确的但我的口头序列列举错了。让我们信任代码用代码来验证# 我们写一个函数来生成前n个看看 def generate_first_n(n, primes): dp [1] * n pointers [0] * len(primes) for i in range(1, n): next_candidates [dp[pointers[j]] * primes[j] for j in range(len(primes))] next_val min(next_candidates) dp[i] next_val for j in range(len(primes)): if dp[pointers[j]] * primes[j] next_val: pointers[j] 1 return dp primes [2, 7, 13, 19] first_15 generate_first_n(15, primes) print(“前15个谦虚数字”, first_15)输出会是[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32, 38, 49, 52]看第10个是26第11个是28第12个是32。所以最初我口算的第10个是32是错误的。这里得到一个重要教训对于序列生成类问题哪怕逻辑清晰也一定要用代码或严谨的模拟进行验证人脑容易在中间步骤出错。现在我们来逐行分析上面的核心代码dp [1] * n: 初始化结果数组第一个数一定是1。pointers [0] * len(primes): 初始化指针数组每个质数最初都指向dp[0]即1。for i in range(1, n): 循环生成剩下的 n-1 个数字。next_candidates [dp[pointers[j]] * primes[j] for j in range(len(primes))]:关键行。对于每个质数primes[j]用其当前指针指向的dp值相乘得到该质数路径上的下一个候选值。这生成了 k 个候选值。next_val min(next_candidates): 从 k 个候选值中选出最小的它就是整个序列的下一个数。dp[i] next_val: 将找到的最小值存入结果数组。for j in range(len(primes)): if dp[pointers[j]] * primes[j] next_val: pointers[j] 1:另一个关键行。遍历所有质数如果某个质数计算出的候选值等于刚才入选的next_val说明这个质数“贡献”了当前值。那么对于这个质数来说它用来乘的基数dp[pointers[j]]已经用过了需要将指针后移指向dp中下一个更大的数以便在下一轮生成新的、更大的候选值。这里有一个极其关键的细节为什么是if ... next_val而不是if ... next_val并且所有等于的指针都要后移因为可能存在多个不同的质数乘以它们各自指针指向的dp值后得到了相同的next_val。例如质数集合为[2, 7]dp序列中有[1, 2, 4, 7, 8, 14...]。当dp中有2和7时对于质数7指针指向dp[0]1候选值为1*77。对于质数2指针指向dp[2]4候选值为4*28。此时next_val是7。只有质数7的候选值等于7所以只移动质数7的指针。下一轮质数7的指针指向了dp[1]2候选值变为2*714。质数2的候选值还是8。next_val是8移动质数2的指针。如果我们在第一轮错误地移动了质数2的指针因为它候选值是8 7就会导致序列错误。所以必须只移动那些候选值恰好等于当前最小值的指针并且可能有多个指针需要移动。4. 性能优化从 O(n*k) 到 O(n log k) 的飞跃上面的基础算法时间复杂度是 O(n * k)因为每一轮我们都要遍历 k 个质数来求最小值和更新指针。当 k 很大时比如质数集合有上百个这个操作可能成为瓶颈。在蓝桥杯等竞赛中n 和 k 都可能达到 10^5 量级O(n*k) 是不可接受的。如何优化核心在于每一轮我们只需要知道 k 个候选值中的最小值以及是哪个或哪些质数产生了这个最小值。这是一个典型的动态获取最小值并更新的场景完美契合优先队列堆Heap的数据结构。我们可以维护一个最小堆堆中的每个元素是一个三元组(value, prime, pointer_index)。value: 候选值即dp[pointer_index] * prime。prime: 产生这个候选值的质数。pointer_index: 该质数当前指向的dp数组中的索引。算法优化步骤初始化堆。将每个质数p与初始指针0指向dp[0]1生成的候选值(1 * p, p, 0)加入最小堆。循环 n-1 次因为第一个数1已知 a. 弹出堆顶元素得到当前最小的候选值val以及对应的质数p和指针索引idx。 b. 如果val不等于dp数组的最后一个元素为了避免重复后面会解释则将val加入dp。 c. 无论是否加入dp都需要为这个质数p生成下一个候选值将指针idx加 1计算新的候选值new_val dp[idx] * p然后将(new_val, p, idx)压入堆中。循环结束后dp[n-1]即为所求。为什么这样更快使用堆后每次获取最小值的时间复杂度是 O(log k)更新弹出后压入新元素也是 O(log k)。所以总时间复杂度从 O(n * k) 优化到了 O(n log k)。当 k 较大时提升非常显著。优化后的代码实现import heapq def nth_super_ugly_number_heap(n, primes): dp [1] * n # 堆中元素 (value, prime, index) heap [] # 初始化堆加入每个质数对应的第一个候选值 for prime in primes: # (候选值 质数 在dp中的指针索引) heapq.heappush(heap, (prime, prime, 0)) # 初始值 1 * prime, 指针指向0 for i in range(1, n): # 弹出当前最小候选值 val, prime, idx heapq.heappop(heap) # 关键去重因为不同的质数路径可能产生相同的值 # 例如2*714, 7*214。如果dp[-1]已经是14那么这个14就是重复的 if val ! dp[i-1]: dp[i] val else: # 如果重复则当前循环不增加新的dp值i需要回退一步 i - 1 # 这是一个需要注意的细节更好的写法是循环直到找到不重复的值 # 为刚才弹出元素的质数生成下一个候选值并加入堆 new_idx idx 1 new_val dp[new_idx] * prime # dp[new_idx] 一定已经存在因为new_idx i heapq.heappush(heap, (new_val, prime, new_idx)) return dp[n-1]注意上面的简化版代码在遇到重复值时通过i - 1来处理这可能会让循环逻辑稍微复杂。更鲁棒的做法是使用一个while循环来确保每次迭代都得到一个唯一的dp[i]def nth_super_ugly_number_heap_robust(n, primes): dp [0] * n dp[0] 1 heap [] for prime in primes: heapq.heappush(heap, (prime, prime, 0)) # (value, prime, index) for i in range(1, n): # 循环直到找到一个不重复的值 while True: val, prime, idx heapq.heappop(heap) if val ! dp[i-1]: dp[i] val break # 如果重复则用同一个质数生成下一个候选值重新入堆 idx 1 heapq.heappush(heap, (dp[idx] * prime, prime, idx)) # 为当前找到的值的生成路径继续添加下一个候选值 # 注意这里我们不知道val是由哪个prime产生的因为可能多个prime产生相同的val # 所以我们需要在弹出时立即为其生成下一个。但上面的while循环里重复的情况已经处理了。 # 对于找到的非重复val产生它的那个质数已经在while循环中被弹出了我们需要为它补上下一个候选。 # 更清晰的写法是在while循环内部无论是否重复都为弹出的质数生成下一个候选并入堆。 # 让我们重构一下 return dp[n-1]让我们写出最终清晰的堆优化版本import heapq def nth_super_ugly_number_heap_final(n, primes): dp [0] * n dp[0] 1 # 堆元素: (value, prime, index) heap [] for prime in primes: heapq.heappush(heap, (prime, prime, 0)) idx_map {prime: 0 for prime in primes} # 也可以用一个数组这里用字典更直观 for i in range(1, n): # 获取当前最小候选值 val, prime, idx heap[0] # 如果这个值和dp中上一个值相同则它是重复的我们需要弹出并更新这个质数的下一个候选 while val dp[i-1]: heapq.heappop(heap) # 为这个质数计算下一个候选 idx 1 next_val dp[idx] * prime heapq.heappush(heap, (next_val, prime, idx)) val, prime, idx heap[0] # 再看新的堆顶 # 此时堆顶的值一定是新的最小值 dp[i] val # 弹出当前堆顶即我们刚放入dp的值对应的那个元素 heapq.heappop(heap) # 为这个质数生成下一个候选值并加入堆 idx 1 next_val dp[idx] * prime heapq.heappush(heap, (next_val, prime, idx)) return dp[n-1]这个版本逻辑更清晰始终维护堆顶是最小候选值。如果堆顶值重复就不断弹出并更新对应的质数路径直到堆顶是一个新值。然后将其放入dp并立即为该质数生成下一个候选值入堆。5. 边界条件、易错点与调试技巧即使理解了算法实现时也常常会掉进坑里。下面是我在多次实现和调试中总结的几个关键点1. 去重是重中之重这是最容易出错的地方。在基础的多指针方法中我们通过if dp[pointers[j]] * primes[j] next_val:来移动指针这隐式处理了重复如果多个质数产生了相同的next_val它们会同时移动指针而dp数组只记录一个next_val。所以基础方法天然避免了重复值进入dp。但在堆优化方法中我们必须显式处理重复。因为堆里可能同时存在多个相同的候选值来自不同的质数路径。如果我们不检查就弹出堆顶并放入dp就会导致dp中出现重复数字使得序列错误最终结果偏大。上面给出的堆优化最终版其while val dp[i-1]循环就是干这个的。2. 整数溢出问题题目通常要求返回第 n 个谦虚数字n 可能很大比如 100000而质数集合可能包含像 2 这样的小质数。第 n 个数字的值可能会非常大超出 32 位整数int的范围。在 Python 中整数是任意精度的所以没问题。但在 C 或 Java 中你需要使用long long(C) 或long(Java) 来存储dp数组和中间计算结果。这是一个常见的陷阱尤其是在写基础的多指针版本时dp[pointers[j]] * primes[j]这个乘法可能在你意识到之前就溢出了。3. 指针索引的边界在基础多指针方法中pointers[j]最大会增加到n-1因为我们需要生成 n 个数字。所以dp数组的大小必须是 n并且pointers[j]的访问不会越界。在堆优化版本中我们为质数生成下一个候选值时需要访问dp[idx]这里的idx也必须确保小于当前已经生成的dp长度。由于我们的逻辑是生成一个dp[i]后才为对应的质数计算基于dp[i]的下一个候选所以idx在加1后是等于i的此时dp[idx]是刚刚被赋值的dp[i]是有效的。但必须确保循环顺序正确。4. 初始化的细节谦虚数字序列的第一个数字通常是 1无论质数集合是什么。所以dp[0] 1。在堆初始化时我们放入的是(1 * prime, prime, 0)即(prime, prime, 0)。这里的指针索引 0 指向dp[0]即1。调试技巧小数据模拟用很小的 n 和质数集合比如n5, primes[2, 3]手动模拟算法过程与你的程序输出对比。丑数序列是[1, 2, 3, 4, 6]看看你的程序能不能得到。打印中间状态在循环中打印每一轮后的dp数组、指针数组或堆的内容这能帮你清晰看到算法是如何一步步构建序列的哪里出现了重复或错误的值。对比两种方法实现基础的多指针方法和堆优化方法用相同的输入测试看结果是否一致。如果不一致就是有 bug。关注去重特意测试质数集合有公倍数的情况例如primes[2, 4]虽然4不是质数但可以测试或者primes[2, 6]看你的算法是否能正确处理像 824 和 42这样的重复生成情况。6. 举一反三算法模型的扩展与应用掌握了“谦虚数字/超级丑数”的解法你其实掌握了一把钥匙可以解开一系列同构问题。它们的核心都是多路归并。1. 丑数 II (Ugly Number II)这是最经典的版本质数集合固定为{2, 3, 5}。解法一模一样只是primes [2, 3, 5]。这是 LeetCode 上的一道经典题。2. 查找和最小的 K 对数字 (Find K Pairs with Smallest Sums)LeetCode 373。给定两个升序数组 nums1 和 nums2以及一个整数 k找到和最小的 k 个数对(u, v)其中u来自 nums1v来自 nums2。 你可以把每个 nums1[i] 想象成一个“质数”把 nums2 想象成初始的dp数组实际上初始是nums2[0]。那么所有数对的和nums1[i] nums2[j]就构成了 k 个有序链表i 从 0 到 len(nums1)-1。你需要合并这 k 个链表的前 k 个最小和。这完全就是多路归并用堆来优化。3. 有序矩阵中第 K 小的元素 (Kth Smallest Element in a Sorted Matrix)LeetCode 378。给定一个 n x n 矩阵每行每列都升序排序找到第 k 小的元素。 你可以把矩阵的每一行看作一个有序链表。那么问题就转化为在 n 个有序链表中找到第 k 小的元素。同样使用最小堆初始将每行的第一个元素入堆然后每次弹出最小值并将该行下一个元素入堆。4. 拼接最大数 (Create Maximum Number)这是一个更复杂的变体但核心思想里也有多路归并的影子需要结合单调栈。这些问题的共性你有多个有序的序列或可以生成有序序列的源头。你需要按某种全局顺序通常是升序从这些序列中逐个取出元素。每次取出当前最小的元素后需要从该元素所在的序列中补充下一个候选元素。识别出这类模式你就能快速套用“多指针堆”的模板大大提升解题速度。7. 蓝桥杯赛场实战策略与时间管理在蓝桥杯这样的竞赛中遇到“谦虚数字”这类题如何快速、准确地拿分1. 快速识别题型看到“第 n 个满足某种特定因数性质的数”立刻联想到“丑数”模型。再确认一下是否只包含给定的质因数如果是那就是超级丑数直接套用。2. 选择实现方法如果质数集合大小 k 很小比如 10直接用基础的多指针 O(n*k) 方法。代码简单不易出错。如果 k 比较大几十甚至上百或者题目数据范围暗示 n 和 k 都可能很大必须使用堆优化 O(n log k) 方法。在竞赛中为了稳妥只要 k 20我通常就直接上堆优化。3. 注意数据范围与类型仔细看题目给出的 n 和质数集合元素的范围。估算一下第 n 个数的最大值可能有多大以此决定使用哪种整数类型Python 自动处理C/Java 用 long long。4. 编写与测试先写基础版本如果时间允许可以先写出逻辑清晰的基础多指针版本用样例测试通过。这能确保你的核心逻辑正确。再优化如果基础版本可能超时再改写成堆优化版本。改写时务必仔细处理去重逻辑这是堆版本最容易出错的地方。设计临界测试测试 n1应该返回 1。测试质数集合包含 1 个元素比如primes[2]那么结果应该是 2^(n-1)。检查你的程序在 n 较大时是否溢出或超时。测试质数集合有重复值或能产生很多重复候选的情况例如primes[2, 4, 8]。确保序列没有重复。5. 时间管理这类题目属于“会者不难难者不会”。如果你熟悉这个模型5-10分钟就能写出代码。如果不熟悉可能卡上半小时也毫无头绪。因此平时积累一定要把丑数、超级丑数、多路归并这类经典模型刷熟理解透彻做到看到题目就能反应。赛场策略如果一开始没思路不要死磕。先读题判断题型如果感觉像某个经典模型但一时想不起可以先做其他题也许在做其他题的过程中会突然灵感闪现。我个人在第一次比赛遇到类似题目时就因为没想起“多路归并”这个模型用了暴力筛法结果只过了小数据点丢了大部分分数。后来专门总结了这类问题以后再遇到就成送分题了。所以算法的积累不在于刷题数量而在于对典型模型的理解深度和举一反三的能力。“谦虚数字”这道题就是一个绝佳的学习多路归并思想的切入点。
)
