📖 前言 | 丑数不丑，思路要秀 ✨

哈喽各位算法小伙伴们～ 今天咱们来唠唠算法圈里大名鼎鼎的「丑数家族」👨‍👩‍👧‍👦！

你可能会问：啥是丑数？长得丑的数字？🤔

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} ...

哎？等等！🧐怎么出现了两个 6？

• 2 × 3 = 6

• 3 × 2 = 6

重复了！这可不行，重复的丑数会让我们的答案出错～

⚡ 神来之笔：用「最大质因子」去重！🎯

这时候就轮到我们的「最大质因子限制法」登场啦！🎉

💡 核心思想

每个丑数只能乘以大于等于它「最大质因子」的质数！

这样就能保证每个丑数只被生成唯一一次，完美去重～

啥意思？举几个栗子 🌰：

为什么这样就不会重复了？🤔

因为我们规定了「只能往大的质因子乘」，相当于给生成路径定了一个单向规则：

• 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++ 代码实现 | 堆解法

话不多说，上代码！👇

#include<iostream>#include<queue>#include<vector>usingnamespacestd;intnthUglyNumber(intn){// 🎯 小顶堆：每次取出最小值// greater<int> 让堆变成「小顶堆」（默认是大顶堆哦）priority_queue<longlong,vector<longlong>,greater<longlong>>minHeap;// 🌱 初始状态：第一个丑数是 1minHeap.push(1);longlongans=0;// 🔄 弹出 n 次，第 n 次就是答案for(inti=0;i<n;i++){ans=minHeap.top();// 取出当前最小丑数minHeap.pop();// 弹出堆顶// 🧪 根据最大质因子判断能乘哪些数if(ans%5==0){// 最大质因子是 5 → 只能乘 5minHeap.push(ans*5);}elseif(ans%3==0){// 最大质因子是 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;}

🔍 代码细节解读

⚠️注意判断顺序：一定要先判断 5，再判断 3，最后是 2！
因为能被 5 整除的数也可能被 3 或 2 整除（比如 30），但它的最大质因子是 5 哦～

⏱️ 复杂度分析

💬 说实话，堆解法的效率确实不如经典的「三指针 DP」高，但胜在思路直观、好理解，面试的时候想不起来 DP 写法，用堆也能 AC！而且逼格满满～ 😎

🚀 第二关：超级丑数 | 多指针 DP 大法

🎯 题目升级

给你一个整数n和一个整数数组primes，返回第n个超级丑数。

超级丑数是指所有质因数都在质数数组primes中的正整数。

示例：输入n = 12, primes = [2,7,13,19]，输出32

简单说就是：丑数 Ⅱ 是固定的 [2,3,5] 三个质因子，超级丑数是给你任意一组质因子！

那堆解法还能用吗？—— 当然能用！把判断逻辑改成遍历 primes 数组就行～

但是！堆解法有个问题：效率不够高🐢

那有没有更快的方法？—— 有！多指针动态规划！🚀

💡 多指针 DP 思路 | 优雅永不过时

还记得丑数 Ⅱ 的经典三指针解法吗？我们把它扩展到 k 个指针就行啦～

🎯 核心思想

• 我们维护一个结果数组 dp，dp[i]表示第 i+1 个丑数

• 每个质数对应一个指针，指向它当前「乘到」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

#include<iostream>#include<vector>#include<climits>usingnamespacestd;intnthSuperUglyNumber(intn,vector<int>&primes){intk=primes.size();// k 个质因子// 📦 dp 数组：dp[i] 表示第 i+1 个超级丑数vector<longlong>dp(n);dp[0]=1;// 第一个丑数是 1// 🎯 指针数组：每个质数对应一个指针vector<int>pointers(k,0);// 全部初始化为 0for(inti=1;i<n;i++){// 🔍 找出所有候选值中的最小值longlongminVal=LLONG_MAX;for(intj=0;j<k;j++){longlongcandidate=primes[j]*dp[pointers[j]];if(candidate<minVal){minVal=candidate;}}dp[i]=minVal;// 存入第 i 个丑数// 📍 所有生成了最小值的指针，都往后挪一位（去重！）for(intj=0;j<k;j++){if(primes[j]*dp[pointers[j]]==minVal){pointers[j]++;}}}return(int)dp[n-1];}// 🧪 测试一下intmain(){vector<int>primes={2,7,13,19};cout<<"第 12 个超级丑数："<<nthSuperUglyNumber(12,primes)<<endl;// 输出 32vector<int>primes2={2,3,5};cout<<"第 10 个丑数（普通丑数）："<<nthSuperUglyNumber(10,primes2)<<endl;// 输出 12return0;}

🔍 代码细节解读

🐛踩坑提醒：

• 指针数组的长度是primes.size()，不是 n！别搞混了～

• ans 的初始化要注意，别写成 0 了，会导致越界或者结果错误

• 多个指针可能同时命中最小值，必须全部后移，否则会有重复丑数

⏱️ 复杂度对比

💡 其中 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 个），总共有 a+b+c 个石子，每轮消耗 2 个，所以除以 2 就是答案～

✨ 终极公式

⎧ a + b , 当 c ≥ a + b ans = ⎨ ⎩ (a + b + c)/2 , 当 c < a + b

是不是很巧妙？一道看似复杂的题，想通了就是一行公式的事～ 🎯

📝 总结 | 今日收获满满！🎁

好啦，今天的算法之旅就到这里～ 咱们来盘点一下收获：

✅ 知识点清单

💡 心得体会

1. 堆是个好东西🎯：找最值的场景优先想想堆，虽然不是最优解，但思路直观好写

2. 去重是门艺术🎨：无论是堆解法的「最大质因子限制」，还是 DP 的「多指针同时后移」，去重都是关键

3. DP 永远的神⚡：多指针 DP 把时间复杂度从 O (n log n) 降到 O (nk)，优雅又高效

4. 数学思维很重要🧠：有些题看似是算法题，其实想通了就是个数学公式

🌟 写在最后

算法这条路，就像爬楼梯一样，一步一个脚印 👣

今天搞懂了丑数家族，明天就能挑战更难的题目！

记住：代码不会骗人，你付出的每一分努力，都会在 AC 的那一刻给你回报～💪

如果这篇博客对你有帮助，别忘了点赞👍 收藏⭐ 关注👀三连哦～

咱们下期再见！拜拜～ 👋🎉

📌往期精彩回顾

• 「动态规划入门到精通」

• 「二叉树的 10 种遍历方式」

• 「回溯算法套路总结」

💬 有问题欢迎在评论区留言，看到都会回复～