第n个丑数从暴力枚举到动态规划多指针的学习笔记在算法训练与工程实现中“以最小代价生成目标序列”是一类非常典型的优化场景。第n个丑数问题看似简单却能很好地体现从暴力思路到线性复杂度、从正确性到效率的完整思考路径也能映射出实际工程中避免无效计算、精准控制状态、减少冗余操作的设计思想。本文以朴素推导为主不做过度包装专注思路演进与细节理解。一、问题回顾给定整数 n返回第 n 个丑数。丑数定义只包含质因数 2、3、5 的正整数1 是第一个丑数。前几项丑数1, 2, 3, 4, 5, 6, 8, 9, 10, 12, …要求在 n 较大时如 10³、10⁴、10⁵ 级别仍能稳定、高效地给出结果。二、最直观思路暴力判断从正确性出发最容易想到的做法是从 1 开始逐个遍历整数对每个数判断它是否只由 2、3、5 因子构成统计是丑数的个数直到找到第 n 个。核心判断逻辑伪代码思路bool isUgly(int x) { if (x 0) return false; while (x % 2 0) x / 2; while (x % 3 0) x / 3; while (x % 5 0) x / 5; return x 1; }存在的问题绝大多数数字都不是丑数会做大量无效除法与判断数字越大非丑数密度越高浪费的计算量越大时间复杂度不可控本质是用“筛选”代替“生成”在大规模场景下不具备实用价值。这也是很多算法题的共同特点能做对 ≠ 能用尤其在对延迟、吞吐量有要求的场景中必须从源头减少无效操作。三、从定义反推丑数的生成性质回到定义丑数只由 2、3、5 相乘得到且 1 是基础丑数。可以直接得出一条关键性质所有丑数都可以由更小的丑数 ×2 / ×3 / ×5 得到。这意味着我们不需要去判断任何一个数是不是丑数只需要从已有的丑数里生成下一个。思路立刻升级从“遍历判断”变成“定向生成有序维护”。但随之而来两个问题生成的数会乱序无法直接取第 n 个不同路径会生成相同数字如 2×363×26存在重复。四、动态规划 多指针精准生成与去重为了只生成丑数、按序生成、不重复生成可以采用动态规划配合多指针的方案。这套方案的本质是用空间记录状态用指针控制迭代用取最小保证有序用多分支判断完成去重。1. 状态设计定义数组dpdp[i]表示第i1个丑数初始化dp[0] 1对应第一个丑数。2. 指针的意义既然每个新丑数只能来自某个旧丑数 ×2某个旧丑数 ×3某个旧丑数 ×5我们用三个指针分别标记当前应该参与乘法的位置p2下一个要 ×2 的丑数下标p3下一个要 ×3 的丑数下标p5下一个要 ×5 的丑数下标初始时都指向 0即从第一个丑数开始。3. 递推规则对每一个新位置dp[i]计算三个候选值num2 dp[p2] * 2num3 dp[p3] * 3num5 dp[p5] * 5取三者最小值作为当前丑数保证严格递增如果当前丑数等于某个候选值就将对应指针后移一位若等于num2p2若等于num3p3若等于num5p5这里必须使用独立的 if 而非 else if目的是当多个候选值相等时如 6 同时由 ×2 和 ×3 得到多个指针同时后移从根源上去重避免后续重复生成同一数字。五、实现代码CclassSolution{public:intnthUglyNumber(intn){if(n1)return1;vectorintdp(n);dp[0]1;intp20,p30,p50;for(inti1;in;i){intnum2dp[p2]*2;intnum3dp[p3]*3;intnum5dp[p5]*5;dp[i]min(min(num2,num3),num5);if(dp[i]num2)p2;if(dp[i]num3)p3;if(dp[i]num5)p5;}returndp[n-1];}};六、复杂度与可扩展性思考时间复杂度只进行一轮从 1 到 n-1 的遍历每一步仅包含固定次数的乘法、比较、指针移动时间复杂度为O(n)是该问题理论下界。空间复杂度使用长度为 n 的 dp 数组保存历史丑数空间复杂度O(n)。在工程视角下如果 n 上限已知且不大这种空间换时间的方式非常划算若追求极致空间可以只保留最近几个关键值但会明显降低可读性与可维护性除非资源极度受限否则不建议。可扩展启发这套思路不局限于丑数只要目标序列满足由基础因子从已有元素生成且需要有序、不重复都可以使用动态规划记录状态 多指针控制迭代位置 取最小保证有序。例如超级丑数质因数不限于 2、3、5某些带限制的倍数序列生成流式生成有序目标集合都可以在这套框架上扩展只需要调整指针数量与候选生成规则。七、小结第 n 个丑数从暴力到最优解的过程本质是三次思维升级从**“筛选所有数”升级为“只生成目标数”**从**“无序生成”升级为“按序生成”**从**“可能重复”升级为“精准去重”**。动态规划多指针并没有复杂数学推导而是用最朴素的方式把每一步多余计算都砍掉只保留必要的状态与转移。这种思路在算法训练中是基础在实际工程中同样适用——很多高性能逻辑并不是靠花哨技巧而是靠精准定义状态、严格控制迭代、彻底消除无效计算来实现的。手动模拟前 10 个丑数的生成过程观察指针移动与去重逻辑能更稳定地掌握这一类生成型问题的通用解法。