题目来源
- 来源：力扣264
题目描述
描述：
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
例如：15是3*5，9是3*3，15和9都是丑数示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明: 1 是丑数。
n 不超过1690。
解法分析
- 题目要求：第k个丑数。所以我们需要求丑数的升序序列的获取方式。
首先，分析丑数的获取方式
- 由第一个丑数1，分别于三个质因数相乘，得到三个丑数，然后排序，得到1、2、3、5.
- 然后对第二个丑数2，再次进行一步骤的操作，得到丑数4、6、10.升序排列得到1、2、3、4、5、6、10.
- 再对第三个丑数进行一步骤的操作，再对整体的数列进行排序，即可得到新的丑数序列。
- 丑数既然可以通过这种方式获得，针对题目要求，可以进行一些修改，即可得到第k个丑数。
实现方式思路如下，这里举个例子
- 对于第一个质因数，分别和2、3、5相乘，取到最小的2，作为第二个质因数，然后，由于1已经和质因数2相乘得到丑数，这时，1不需要和质因数2再做乘法操作来获取丑数
- 所以，第二次操作，就是1和3、5相乘，而质因数2和第二个丑数相乘，取到最小的3作为第三个丑数，然后，由于1已经和质因数3相乘得到丑数，这时，1不需要和质因数3再做乘法操作来获取丑数
- 所以，第三次操作，就是1和5相乘，而质因数2、3和第二个丑数相乘，取到最小的4作为第四个丑数，然后，由于2已经和质因数2相乘得到丑数，这时，2不需要和质因数2再做乘法操作来获取丑数
- 依次类推，即可依次得到丑数序列。
图解
丑数.png
算法实现
- 由于需要分别标记质因数2、3、5分别和第几个丑数进行乘法运算，所以，可以定义三个指针对应三个质因数，指向数组中的位置。
- 这样，每次判断出，取到的值是和某个质因数反应，就可以将该质因数对应的指针向后移动一位。
代码实现（Java）
public int nthUglyNumber(int n) {
//定义一个数组存储丑数序列
int[] dp = new int[n];
dp[0] = 1;
int min = Integer.MAX_VALUE;
//定义三个指针，分别对应质因数2、3、5.
int i2 = 0,i3 = 0,i5 = 0;
for (int i = 1; i < n; i++) {
//取得最小值作为下一个丑数
min = Math.min(dp[i2] * 2,Math.min(dp[i5] * 5,dp[i3] * 3));
//判断是那一个质因数参与得到丑数，将其指针向后移动一位
if(min == dp[i3] * 3) i3++;
if(min == dp[i5] * 5) i5++;
if(min == dp[i2] * 2) i2++;
//将丑数存入丑数序列
dp[i] = min;
}
return dp[n - 1];
}
