LeetCode题练习与总结：丑数 Ⅱ--264
一、题目描述
给你一个整数 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
二、解题思路
- 创建一个动态规划数组
dp，其中dp[i]表示第i个丑数。初始化dp[1] = 1，因为 1 通常被视为丑数。 - 创建三个指针
p2,p3,p5，分别表示下一个丑数可以通过乘以 2、3 或 5 得到。初始时，这三个指针都指向 1。 - 对于每个
i（从 2 到n），计算dp[i]的值，它是min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)。 - 更新
p2、p3和p5指针，以指向下一个应该乘以 2、3 或 5 的丑数。 - 返回
dp[n]作为结果。
三、具体代码
class Solution {public int nthUglyNumber(int n) {int[] dp = new int[n + 1];dp[1] = 1;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);if (dp[i] == num2) p2++;if (dp[i] == num3) p3++;if (dp[i] == num5) p5++;}return dp[n];}
}
在这个实现中，我们通过动态规划的方法，逐步构建出丑数序列。每个指针 p2, p3, p5 保证不会重复计算同一个丑数，并且能够保证丑数序列的顺序。
四、时间复杂度和空间复杂度
1. 时间复杂度
- 初始化
dp数组需要 O(n) 的时间，因为需要将dp[1]设置为 1，其余dp[i]初始化为 0。 - 遍历
dp数组，计算每个dp[i]的值，这个操作需要 O(n) 的时间，因为需要从 2 遍历到 n。 - 在每次遍历中，计算
num2,num3,num5以及Math.min函数的调用都是常数时间操作，因此对于每次迭代，时间复杂度是 O(1)。 - 总的时间复杂度是 O(n) + O(n) * O(1) = O(n)。
2. 空间复杂度
dp数组需要 O(n) 的空间，因为需要存储 n 个丑数。- 除了
dp数组，我们只使用了几个额外的变量（p2,p3,p5,num2,num3,num5），它们都是常数空间。 - 因此，总的空间复杂度是 O(n)。
五、总结知识点
-
类定义：
class Solution定义了一个名为Solution的类。 -
方法定义：
public int nthUglyNumber(int n)定义了一个公共方法nthUglyNumber，它接受一个整数参数n并返回一个整数。 -
数组的使用：
int[] dp = new int[n + 1];创建了一个整数数组dp，用于动态规划，长度为n + 1以存储从第 1 个到第 n 个丑数。 -
基本循环结构：
for (int i = 2; i <= n; i++)使用了一个for循环来迭代数组dp的索引，从 2 到 n。 -
条件判断：
if (dp[i] == num2) p2++;等条件判断用于检查当前的丑数是通过乘以 2、3 或 5 得到的，并相应地更新指针。 -
数学运算：使用乘法
*和最小值函数Math.min来计算可能的丑数。 -
指针的概念：
p2,p3,p5作为指针，分别跟踪下一个应该乘以 2、3 或 5 的丑数的位置。 -
数组的索引访问：通过
dp[p2],dp[p3],dp[p5]等方式访问数组元素，以计算下一个可能的丑数。 -
变量赋值：
dp[i] = Math.min(Math.min(num2, num3), num5);等语句展示了如何将计算结果赋值给数组元素。
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。