丑数家族大揭秘从堆解法到多指针DP手撕两道经典算法题 前言 | 丑数不丑思路要秀 ✨Bilibili 同步视频 第一关丑数 Ⅱ | 小顶堆的优雅演绎 题目描述 思路一暴力NONO我们用「生成法」 生成过程初探⚡ 神来之笔用「最大质因子」去重 生成树长啥样ASCII 图解️ 数据结构选型小顶堆优先队列 C 代码实现 | 堆解法 代码细节解读⏱️ 复杂度分析 第二关超级丑数 | 多指针 DP 大法 题目升级 多指针 DP 思路 | 优雅永不过时 核心思想 举个栗子走一遍 C 代码实现 | 多指针 DP 代码细节解读⏱️ 复杂度对比 彩蛋石子游戏脑筋急转弯 思路分析情况一最大堆 ≥ 另外两堆之和情况二最大堆 另外两堆之和✨ 终极公式 总结 | 今日收获满满✅ 知识点清单 心得体会 写在最后 前言 | 丑数不丑思路要秀 ✨哈喽各位算法小伙伴们 今天咱们来唠唠算法圈里大名鼎鼎的「丑数家族」‍‍‍你可能会问啥是丑数长得丑的数字NO NO NO丑数一点都不丑它可是算法面试的常客、LeetCode 的座上宾、大厂面试官的心头好 丑数定义小课堂丑数就是只包含质因数2、3、5的正整数。比如1, 2, 3, 4, 5, 6, 8, 9, 10, 12...而7、11、13这些就不是丑数啦因为它们自带别的质因数今天咱们就从「丑数 Ⅱ」这道题切入先搞一个小顶堆的酷炫解法然后再升级到「超级丑数」的多指针 DP大法坐稳扶好发车啦 Bilibili 同步视频丑数家族大揭秘从堆解法到多指针DP手撕两道经典算法题 第一关丑数 Ⅱ | 小顶堆的优雅演绎 题目描述给你一个整数n请你找出并返回第n个丑数。示例输入n 10输出12解释[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]是前 10 个丑数第 10 个是 12。 思路一暴力NONO我们用「生成法」最朴素的想法从 1 开始一个个判断是不是丑数数到第 n 个达咩‍♂️这样效率太低了n 一大就 TLE 给你看我们换个思路既然丑数只能由 2、3、5 相乘得到那我们直接「生成」丑数不就完了 生成过程初探想象一下我们有一个魔法集合 里面装着已经生成的丑数初始状态{ 1 } ← 第一个丑数是 1每次我们从集合里拿出最小的那个丑数然后用它分别 ×2、×3、×5生成新的丑数放回集合第1次取出最小值 1 → 生成 2、3、5 → 集合变成 {2, 3, 5} 第2次取出最小值 2 → 生成 4、6、10 → 集合变成 {3, 4, 5, 6, 10} 第3次取出最小值 3 → 生成 6、9、15 → 集合变成 {4, 5, 6, 6, 9, 10, 15} ...哎等等怎么出现了两个 62 × 3 63 × 2 6重复了这可不行重复的丑数会让我们的答案出错⚡ 神来之笔用「最大质因子」去重这时候就轮到我们的「最大质因子限制法」登场啦 核心思想每个丑数只能乘以大于等于它「最大质因子」的质数这样就能保证每个丑数只被生成唯一一次完美去重啥意思举几个栗子 丑数最大质因子可以乘的数生成的新丑数1无特殊处理2、3、52、3、5222、3、54、6、10333、59、15422、3、58、12、2055525633、518、30105550为什么这样就不会重复了因为我们规定了「只能往大的质因子乘」相当于给生成路径定了一个单向规则6 只能通过2 × 3生成因为 2 的最大质因子是 2可以乘 3而不能通过3 × 2生成因为 3 的最大质因子是 3不能乘比它小的 2这样每个丑数就只有唯一一条生成路径重复不存在的 生成树长啥样ASCII 图解用文字画一棵丑数生成树给大家看看 1 /| / | / | 2 3 5 /| / | 4 6 10 9 15 25 /| ... / | 8 12 18 30 ...解读每个节点只能生出「大于等于自身最大质因子」的子节点保证路径唯一不重复是不是瞬间就通透了✨️ 数据结构选型小顶堆优先队列既然每次都要取「最小值」那小顶堆最小优先队列简直是为这道题量身定做的取最小值O (1) 直接看堆顶插入新元素O (log k)k 是堆中元素个数完美匹配我们的需求 C 代码实现 | 堆解法话不多说上代码#includeiostream#includequeue#includevectorusingnamespacestd;intnthUglyNumber(intn){// 小顶堆每次取出最小值// greaterint 让堆变成「小顶堆」默认是大顶堆哦priority_queuelonglong,vectorlonglong,greaterlonglongminHeap;// 初始状态第一个丑数是 1minHeap.push(1);longlongans0;// 弹出 n 次第 n 次就是答案for(inti0;in;i){ansminHeap.top();// 取出当前最小丑数minHeap.pop();// 弹出堆顶// 根据最大质因子判断能乘哪些数if(ans%50){// 最大质因子是 5 → 只能乘 5minHeap.push(ans*5);}elseif(ans%30){// 最大质因子是 3 → 可以乘 3、5minHeap.push(ans*3);minHeap.push(ans*5);}else{// 最大质因子是 2或 1→ 可以乘 2、3、5minHeap.push(ans*2);minHeap.push(ans*3);minHeap.push(ans*5);}}return(int)ans;}// 测试一下intmain(){cout第 10 个丑数是nthUglyNumber(10)endl;// 输出 12cout第 1 个丑数是nthUglyNumber(1)endl;// 输出 1return0;} 代码细节解读关键点说明priority_queue..., greater...C 默认是大顶堆加greater变成小顶堆long long** 类型**丑数增长很快n 大了会溢出 int必须用 long long 「猥琐一波」ans % 5 0** 判断**能被 5 整除说明最大质因子至少是 5只能继续乘 5ans % 3 0** 判断**能被 3 整除但不能被 5 整除最大质因子是 3else 分支最大质因子是 2或者是 1三个都能乘⚠️注意判断顺序一定要先判断 5再判断 3最后是 2因为能被 5 整除的数也可能被 3 或 2 整除比如 30但它的最大质因子是 5 哦⏱️ 复杂度分析维度复杂度说明时间O(n log n)每次弹出 插入都是 O (log n)共 n 次空间O(n)堆中最多存放 O (n) 个元素 说实话堆解法的效率确实不如经典的「三指针 DP」高但胜在思路直观、好理解面试的时候想不起来 DP 写法用堆也能 AC而且逼格满满 第二关超级丑数 | 多指针 DP 大法 题目升级给你一个整数n和一个整数数组primes返回第n个超级丑数。超级丑数是指所有质因数都在质数数组primes中的正整数。示例输入n 12, primes [2,7,13,19]输出32简单说就是丑数 Ⅱ 是固定的 [2,3,5] 三个质因子超级丑数是给你任意一组质因子那堆解法还能用吗—— 当然能用把判断逻辑改成遍历 primes 数组就行但是堆解法有个问题效率不够高那有没有更快的方法—— 有多指针动态规划 多指针 DP 思路 | 优雅永不过时还记得丑数 Ⅱ 的经典三指针解法吗我们把它扩展到 k 个指针就行啦 核心思想我们维护一个结果数组 dpdp[i]表示第 i1 个丑数每个质数对应一个指针指向它当前「乘到」dp 数组的哪个位置每一轮我们计算primes[i] * dp[pointer[i]]取最小值作为下一个丑数谁生成了这个最小值谁的指针就往后挪一位可能多个指针同时挪去重 举个栗子走一遍primes [2, 7, 13, 19]我们来找前几个丑数初始状态 dp [1] pointers [0, 0, 0, 0] ← 四个质数各一个指针都指向第 0 位 第 1 轮 2 * dp[0] 2*1 2 7 * dp[0] 7*1 7 13 * dp[0] 13 19 * dp[0] 19 最小值是 2 → dp [1, 2] 第 0 个指针后移 → pointers [1, 0, 0, 0] 第 2 轮 2 * dp[1] 2*2 4 7 * dp[0] 7 13 * dp[0] 13 19 * dp[0] 19 最小值是 4 → dp [1, 2, 4] 第 0 个指针后移 → pointers [2, 0, 0, 0] 第 3 轮 2 * dp[2] 2*4 8 7 * dp[0] 7 ← 最小 ... 最小值是 7 → dp [1, 2, 4, 7] 第 1 个指针后移 → pointers [2, 1, 0, 0] ...以此类推...是不是很清晰每个指针就像一个「生产线」各自生产自己倍数的丑数我们每次取最便宜最小的那个上架 C 代码实现 | 多指针 DP#includeiostream#includevector#includeclimitsusingnamespacestd;intnthSuperUglyNumber(intn,vectorintprimes){intkprimes.size();// k 个质因子// dp 数组dp[i] 表示第 i1 个超级丑数vectorlonglongdp(n);dp[0]1;// 第一个丑数是 1// 指针数组每个质数对应一个指针vectorintpointers(k,0);// 全部初始化为 0for(inti1;in;i){// 找出所有候选值中的最小值longlongminValLLONG_MAX;for(intj0;jk;j){longlongcandidateprimes[j]*dp[pointers[j]];if(candidateminVal){minValcandidate;}}dp[i]minVal;// 存入第 i 个丑数// 所有生成了最小值的指针都往后挪一位去重for(intj0;jk;j){if(primes[j]*dp[pointers[j]]minVal){pointers[j];}}}return(int)dp[n-1];}// 测试一下intmain(){vectorintprimes{2,7,13,19};cout第 12 个超级丑数nthSuperUglyNumber(12,primes)endl;// 输出 32vectorintprimes2{2,3,5};cout第 10 个丑数普通丑数nthSuperUglyNumber(10,primes2)endl;// 输出 12return0;} 代码细节解读关键点说明dp[0] 1第一个丑数永远是 1这是约定俗成的两层 for 循环外层 n 次内层 k 次k 是质数个数第二个 for 循环关键所有等于最小值的指针都要后移这是去重的核心long long还是那句话丑数增长快防溢出踩坑提醒指针数组的长度是primes.size()不是 n别搞混了ans 的初始化要注意别写成 0 了会导致越界或者结果错误多个指针可能同时命中最小值必须全部后移否则会有重复丑数⏱️ 复杂度对比解法时间复杂度空间复杂度适用场景小顶堆O(nk log n)O(n)思路直观k 较小时可用多指针 DPO(nk)O(n k)效率更高推荐写法 其中 k 是质数数组 primes 的长度。可以看到DP 解法省去了堆的 log n 开销效率直接上一个台阶 彩蛋石子游戏脑筋急转弯题目有三堆石子每一轮你可以从两堆中各拿走 1 个问最多能玩多少轮这道题是个经典的脑筋急转弯咱们也来唠唠 思路分析先给三堆石子排个序a ≤ b ≤ c情况一最大堆 ≥ 另外两堆之和堆1███ (3个) 堆2█████ (5个) 堆3██████████ (10个) a b 8 c 10这种情况最多能玩几轮——a b 轮为啥因为你每次都要从两堆各拿一个而最小的两堆加起来才 8 个用完就没了 最大堆再大也没用因为找不到搭档了 情况二最大堆 另外两堆之和堆1█████ (5个) 堆2███████ (7个) 堆3████████ (8个) a b 12 c 8这种情况呢——(a b c) / 2 轮因为三堆数量比较均衡我们可以合理搭配把所有石子都消耗完或者剩 1 个总共有 abc 个石子每轮消耗 2 个所以除以 2 就是答案✨ 终极公式⎧ a b , 当 c ≥ a b ans ⎨ ⎩ (a b c)/2 , 当 c a b是不是很巧妙一道看似复杂的题想通了就是一行公式的事 总结 | 今日收获满满好啦今天的算法之旅就到这里 咱们来盘点一下收获✅ 知识点清单题目核心解法关键技巧丑数 Ⅱ小顶堆最大质因子限制法去重超级丑数多指针 DP每个质数一个指针最小值后移石子游戏数学脑筋急转弯排序后分两种情况讨论 心得体会堆是个好东西找最值的场景优先想想堆虽然不是最优解但思路直观好写去重是门艺术无论是堆解法的「最大质因子限制」还是 DP 的「多指针同时后移」去重都是关键DP 永远的神⚡多指针 DP 把时间复杂度从 O (n log n) 降到 O (nk)优雅又高效数学思维很重要有些题看似是算法题其实想通了就是个数学公式 写在最后算法这条路就像爬楼梯一样一步一个脚印 今天搞懂了丑数家族明天就能挑战更难的题目记住代码不会骗人你付出的每一分努力都会在 AC 的那一刻给你回报如果这篇博客对你有帮助别忘了点赞 收藏⭐ 关注三连哦咱们下期再见拜拜 往期精彩回顾「动态规划入门到精通」「二叉树的 10 种遍历方式」「回溯算法套路总结」 有问题欢迎在评论区留言看到都会回复