题目
丑数 II:
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是只包含质因数 2、3 和/或 5 的正整数。
示例 1：
输入： n = 10 输出： 12 解释： [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入： n = 1 输出： 1 解释： 1 通常被视为丑数。
提示：
1 <= n <= 1690
题解
解题分析
题解思路
- 定义三个指针 p2, p3, p5;
- 在 2 - n 区间内， 第 N 个丑数值为
dp[n] = min(dp[p2]×2, dp[p3]×3, dp[p5]×5);
- 对应的 p2, p3, p5 指针递增；
- 整个数列其他的数据同理， 具体可以看看代码中的处理
复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)
解题代码
题解代码如下（代码中有详细的注释说明）：
class Solution { public int nthUglyNumber(int n) { int[] dp = new int[n + 1]; // 1 设置默认值 dp[1] = 1 ; // 定义三个指针 p2, p3, p5 int p2 = 1, p3 = 1, p5 = 1; for(int i = 2; i <= n; i++) { // 获取三个指针对应的值 int num2 =dp[p2] * 2, num3 = dp[p3] * 3, num5 = dp[p5] * 5; // 获取最小值 dp[i] = Math.min(Math.min(num2, num3), num5); // p2 累加 if (dp[i] == num2) { p2++; } // p3 累加 if (dp[i] == num3) { p3++; } // p5 累加 if (dp[i] == num5) { p5++; } } return dp[n]; } }
提交后反馈结果：
解题总结
- 本题是一个标准的数列问题，可以通过
动态规划、最小堆方案来解题。
- 在本题目中，其实最难的即使推导出通过三个计数值，以及计算结果进行推导出数列第 n 个值的过程。
- 如果我们在生产或者实际中遇到这个问题，我们可以记住这种模式，首先定位模式，然后进行具体的解题。
