1. 问题定义与数学背景丑数Ugly Number是指只包含质因数2、3或5的正整数。LeetCode第264题要求我们找出第n个丑数。这个问题看似简单但蕴含着深刻的数学原理和算法设计思想。从数学角度看丑数序列可以看作是由1开始不断乘以2、3或5生成的数的集合。前几个丑数是1, 2, 3, 4, 5, 6, 8, 9, 10, 12...。值得注意的是7、11、13等不含2、3、5以外质因数的数不属于丑数。关键性质每个丑数都可以表示为2^a × 3^b × 5^c其中a、b、c是非负整数2. 暴力解法与优化思路2.1 直观的暴力解法最直接的思路是对每个正整数依次判断是否为丑数直到找到第n个为止。判断方法是将数字不断除以2、3、5直到无法整除看最终结果是否为1。def is_ugly(num): for p in [2, 3, 5]: while num % p 0: num num // p return num 1 def nthUglyNumber(n): count 0 num 1 while count n: if is_ugly(num): count 1 num 1 return num - 1这种方法的时间复杂度为O(nlogn)对于较大的n如n1690会非常低效因为需要检查大量非丑数。2.2 动态规划解法更高效的解法是利用动态规划。核心思想是每个丑数都是由前面的某个丑数乘以2、3或5得到的。我们需要维护三个指针分别表示下一个丑数是当前指针指向的丑数乘以对应的质因数。def nthUglyNumber(n): ugly [1] i2 i3 i5 0 for _ in range(1, n): next_ugly min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) ugly.append(next_ugly) if next_ugly ugly[i2]*2: i2 1 if next_ugly ugly[i3]*3: i3 1 if next_ugly ugly[i5]*5: i5 1 return ugly[-1]这个算法的时间复杂度是O(n)空间复杂度也是O(n)效率显著提升。3. 算法细节与实现技巧3.1 指针移动的逻辑三个指针i2、i3、i5的移动是算法的关键。每次生成新的丑数后所有能产生这个最小值的指针都需要前进这样可以避免重复计算和遗漏。例如当next_ugly6时6 2×3 (i2指向3i3指向2)需要同时移动i2和i3因为3×2和2×3都等于63.2 初始化与边界条件初始丑数列表为[1]因为1被定义为第一个丑数三个指针初始都指向0即第一个丑数需要特别注意n1时的直接返回3.3 空间优化虽然我们使用了O(n)的空间存储丑数序列但实际上可以优化到O(1)空间因为我们只需要保存最近的几个丑数用于比较。不过在大多数实现中保留完整序列更便于理解和调试。4. 数学证明与正确性验证4.1 算法正确性证明动态规划解法的正确性基于以下两个性质每个丑数除1外都可以表示为较小丑数乘以2、3或5通过维护三个指针我们确保每个乘积都被考虑到且按顺序生成4.2 数学归纳法验证基础情况第一个丑数1正确 归纳假设前k个丑数正确生成 归纳步骤第k1个丑数是min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)由归纳假设这三个乘积都是基于正确的丑数生成的且取最小值保证了顺序正确5. 性能分析与优化5.1 时间复杂度对比方法时间复杂度空间复杂度适用场景暴力法O(nlogn)O(1)小规模n动态规划O(n)O(n)通用堆/优先队列O(nlogn)O(n)需要按序生成时5.2 实际运行测试当n1690时暴力法约5秒Python实现动态规划1毫秒5.3 进一步优化思路预计算如果需要多次查询可以预先生成一个足够大的丑数列表数学方法利用丑数的数学性质推导公式但实现复杂并行计算将生成过程分解为独立任务并行执行6. 常见错误与调试技巧6.1 典型错误案例指针移动不全只移动一个指针而忽略其他可能产生相同最小值的指针初始条件错误忘记包含1作为第一个丑数整数溢出当n很大时丑数可能超出整数范围Python无此问题6.2 调试方法打印中间结果输出生成的丑数序列和指针位置小规模测试先验证n10等小规模的正确性边界检查特别测试n1和n2的情况6.3 测试用例设计test_cases [ (1, 1), (2, 2), (10, 12), (20, 36), (1690, 2123366400) ]7. 实际应用与扩展7.1 现实中的应用场景资源分配如任务调度中优先处理简单任务类比丑数的优先级密码学在某些哈希算法中需要生成特定性质的数字游戏开发需要生成特定倍数的分数或奖励7.2 问题变种超级丑数质因数不限于2、3、5而是给定的一组质数丑数II判断一个数是否为丑数按序生成实时生成丑数序列而不预先知道n7.3 扩展思考如何证明丑数序列在正整数集中的密度为0能否找到第n个丑数的闭式表达式如何高效生成前n个丑数的所有质因数分解8. 不同语言实现对比8.1 Python实现特点利用动态数组和min函数使代码简洁def nthUglyNumber(n): ugly [1] i2 i3 i5 0 for _ in range(n-1): u2, u3, u5 ugly[i2]*2, ugly[i3]*3, ugly[i5]*5 umin min(u2, u3, u5) if umin u2: i2 1 if umin u3: i3 1 if umin u5: i5 1 ugly.append(umin) return ugly[-1]8.2 Java实现注意事项需要显式类型声明和数组初始化public int nthUglyNumber(int n) { int[] ugly new int[n]; ugly[0] 1; int i2 0, i3 0, i5 0; for (int i 1; i n; i) { int next Math.min(ugly[i2]*2, Math.min(ugly[i3]*3, ugly[i5]*5)); ugly[i] next; if (next ugly[i2]*2) i2; if (next ugly[i3]*3) i3; if (next ugly[i5]*5) i5; } return ugly[n-1]; }8.3 C实现性能优化可以使用vector并注意避免重复计算int nthUglyNumber(int n) { vectorint ugly(n); ugly[0] 1; int i2 0, i3 0, i5 0; for (int i 1; i n; i) { int u2 ugly[i2] * 2; int u3 ugly[i3] * 3; int u5 ugly[i5] * 5; ugly[i] min(u2, min(u3, u5)); if (ugly[i] u2) i2; if (ugly[i] u3) i3; if (ugly[i] u5) i5; } return ugly.back(); }9. 算法可视化理解为了更好理解动态规划解法可以想象有三个队列Q2存储每个丑数×2的结果Q3存储每个丑数×3的结果Q5存储每个丑数×5的结果每次取三个队列头部的最小值作为下一个丑数并将对应的队列指针后移。这种方法避免了排序保证了顺序性。10. 面试技巧与回答策略当面试中被问到这个问题时建议采取以下步骤先明确问题定义和要求提出暴力解法并分析其复杂度指出暴力解法的问题效率低提出动态规划思路并解释三个指针的作用逐步推导算法实现分析时间/空间复杂度讨论可能的优化和变种典型面试问题可能包括如何证明你的算法是正确的如果不允许使用额外空间如何解决如果质因数不限于2、3、5而是任给的如何修改算法在实际编码时我发现最容易出错的地方是三个指针的更新条件。有一次我在白板面试中忘记了同时更新能产生相同最小值的所有指针导致生成的序列缺少某些丑数。这个教训让我更加理解了每个指针独立移动的重要性。
1. 问题定义与数学背景丑数Ugly Number是指只包含质因数2、3或5的正整数。LeetCode第264题要求我们找出第n个丑数。这个问题看似简单但蕴含着深刻的数学原理和算法设计思想。从数学角度看丑数序列可以看作是由1开始不断乘以2、3或5生成的数的集合。前几个丑数是1, 2, 3, 4, 5, 6, 8, 9, 10, 12...。值得注意的是7、11、13等不含2、3、5以外质因数的数不属于丑数。关键性质每个丑数都可以表示为2^a × 3^b × 5^c其中a、b、c是非负整数2. 暴力解法与优化思路2.1 直观的暴力解法最直接的思路是对每个正整数依次判断是否为丑数直到找到第n个为止。判断方法是将数字不断除以2、3、5直到无法整除看最终结果是否为1。def is_ugly(num): for p in [2, 3, 5]: while num % p 0: num num // p return num 1 def nthUglyNumber(n): count 0 num 1 while count n: if is_ugly(num): count 1 num 1 return num - 1这种方法的时间复杂度为O(nlogn)对于较大的n如n1690会非常低效因为需要检查大量非丑数。2.2 动态规划解法更高效的解法是利用动态规划。核心思想是每个丑数都是由前面的某个丑数乘以2、3或5得到的。我们需要维护三个指针分别表示下一个丑数是当前指针指向的丑数乘以对应的质因数。def nthUglyNumber(n): ugly [1] i2 i3 i5 0 for _ in range(1, n): next_ugly min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5) ugly.append(next_ugly) if next_ugly ugly[i2]*2: i2 1 if next_ugly ugly[i3]*3: i3 1 if next_ugly ugly[i5]*5: i5 1 return ugly[-1]这个算法的时间复杂度是O(n)空间复杂度也是O(n)效率显著提升。3. 算法细节与实现技巧3.1 指针移动的逻辑三个指针i2、i3、i5的移动是算法的关键。每次生成新的丑数后所有能产生这个最小值的指针都需要前进这样可以避免重复计算和遗漏。例如当next_ugly6时6 2×3 (i2指向3i3指向2)需要同时移动i2和i3因为3×2和2×3都等于63.2 初始化与边界条件初始丑数列表为[1]因为1被定义为第一个丑数三个指针初始都指向0即第一个丑数需要特别注意n1时的直接返回3.3 空间优化虽然我们使用了O(n)的空间存储丑数序列但实际上可以优化到O(1)空间因为我们只需要保存最近的几个丑数用于比较。不过在大多数实现中保留完整序列更便于理解和调试。4. 数学证明与正确性验证4.1 算法正确性证明动态规划解法的正确性基于以下两个性质每个丑数除1外都可以表示为较小丑数乘以2、3或5通过维护三个指针我们确保每个乘积都被考虑到且按顺序生成4.2 数学归纳法验证基础情况第一个丑数1正确 归纳假设前k个丑数正确生成 归纳步骤第k1个丑数是min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5)由归纳假设这三个乘积都是基于正确的丑数生成的且取最小值保证了顺序正确5. 性能分析与优化5.1 时间复杂度对比方法时间复杂度空间复杂度适用场景暴力法O(nlogn)O(1)小规模n动态规划O(n)O(n)通用堆/优先队列O(nlogn)O(n)需要按序生成时5.2 实际运行测试当n1690时暴力法约5秒Python实现动态规划1毫秒5.3 进一步优化思路预计算如果需要多次查询可以预先生成一个足够大的丑数列表数学方法利用丑数的数学性质推导公式但实现复杂并行计算将生成过程分解为独立任务并行执行6. 常见错误与调试技巧6.1 典型错误案例指针移动不全只移动一个指针而忽略其他可能产生相同最小值的指针初始条件错误忘记包含1作为第一个丑数整数溢出当n很大时丑数可能超出整数范围Python无此问题6.2 调试方法打印中间结果输出生成的丑数序列和指针位置小规模测试先验证n10等小规模的正确性边界检查特别测试n1和n2的情况6.3 测试用例设计test_cases [ (1, 1), (2, 2), (10, 12), (20, 36), (1690, 2123366400) ]7. 实际应用与扩展7.1 现实中的应用场景资源分配如任务调度中优先处理简单任务类比丑数的优先级密码学在某些哈希算法中需要生成特定性质的数字游戏开发需要生成特定倍数的分数或奖励7.2 问题变种超级丑数质因数不限于2、3、5而是给定的一组质数丑数II判断一个数是否为丑数按序生成实时生成丑数序列而不预先知道n7.3 扩展思考如何证明丑数序列在正整数集中的密度为0能否找到第n个丑数的闭式表达式如何高效生成前n个丑数的所有质因数分解8. 不同语言实现对比8.1 Python实现特点利用动态数组和min函数使代码简洁def nthUglyNumber(n): ugly [1] i2 i3 i5 0 for _ in range(n-1): u2, u3, u5 ugly[i2]*2, ugly[i3]*3, ugly[i5]*5 umin min(u2, u3, u5) if umin u2: i2 1 if umin u3: i3 1 if umin u5: i5 1 ugly.append(umin) return ugly[-1]8.2 Java实现注意事项需要显式类型声明和数组初始化public int nthUglyNumber(int n) { int[] ugly new int[n]; ugly[0] 1; int i2 0, i3 0, i5 0; for (int i 1; i n; i) { int next Math.min(ugly[i2]*2, Math.min(ugly[i3]*3, ugly[i5]*5)); ugly[i] next; if (next ugly[i2]*2) i2; if (next ugly[i3]*3) i3; if (next ugly[i5]*5) i5; } return ugly[n-1]; }8.3 C实现性能优化可以使用vector并注意避免重复计算int nthUglyNumber(int n) { vectorint ugly(n); ugly[0] 1; int i2 0, i3 0, i5 0; for (int i 1; i n; i) { int u2 ugly[i2] * 2; int u3 ugly[i3] * 3; int u5 ugly[i5] * 5; ugly[i] min(u2, min(u3, u5)); if (ugly[i] u2) i2; if (ugly[i] u3) i3; if (ugly[i] u5) i5; } return ugly.back(); }9. 算法可视化理解为了更好理解动态规划解法可以想象有三个队列Q2存储每个丑数×2的结果Q3存储每个丑数×3的结果Q5存储每个丑数×5的结果每次取三个队列头部的最小值作为下一个丑数并将对应的队列指针后移。这种方法避免了排序保证了顺序性。10. 面试技巧与回答策略当面试中被问到这个问题时建议采取以下步骤先明确问题定义和要求提出暴力解法并分析其复杂度指出暴力解法的问题效率低提出动态规划思路并解释三个指针的作用逐步推导算法实现分析时间/空间复杂度讨论可能的优化和变种典型面试问题可能包括如何证明你的算法是正确的如果不允许使用额外空间如何解决如果质因数不限于2、3、5而是任给的如何修改算法在实际编码时我发现最容易出错的地方是三个指针的更新条件。有一次我在白板面试中忘记了同时更新能产生相同最小值的所有指针导致生成的序列缺少某些丑数。这个教训让我更加理解了每个指针独立移动的重要性。
