给你一个整数 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
题解
先说明一个概念
每个合数都可以写成几个质数（也可称为素数）相乘的形式 ，这几个质数就都叫做这个合数的质因数。如果一个质数是某个数的因数，那么就说这个质数是这个数的质因数；而这个因数一定是一个质数。（来自于百度百科）
举例
- 1没有质因子。
- 5只有1个质因子，5本身。（5是质数）
- 6的质因子是2和3。(6 = 2 × 3)
- 2、4、8、16等只有1个质因子：2。（2是质数，4 =2²，8 = 2³，如此类推）
- 10有2个质因子：2和5。(10 = 2 × 5)
所以我们知道了，所求数字即为，给定的2、3、5相互组合相乘得到的结果，可以重复相乘，即可以使2x2x2x3x3x5x5x5这样的组合。
而题中所求的第n位即是将所得结果按照从小到大的顺序有序排列的第n位数字，且根据质因数的概念，第一位一定是数字1。
那么，我们可以按照题意按部就班的来求解，结果集的第一位是1，那么结果集此时是【1】
来到第二位。可以是前面的结果集第一位的1×2，也可以是1×3，也可以是1×5，但是按照从小到大的顺序，应该是1×2，此时结果集为【1,2】
来到第三位，因为前面的1×2已经算过，可以直接忽略，那么我们要比较的就是2×2（此处的2是前面得到1×2的结果的2，不是自然数递增的2），和上次剩下的1×3，1×5，显然结果应该是3，此时的结果集【1,2,3】
来到第四位需要比较的是2×2,2×3,1×5,显然应该是4，此时的结果集为【1,2,3,4】
后面依次：
第五位 3×2,2×3,1×5，结果集【1,2,3,4,5】
第六位 3×2,2×3,2×5，结果集是【1,2,3,4,5,6】，而此时的3×2和2×3都能得到6这个结果，显然是重复的，应该只记一次
第七位 4×2,3×3,2×5，结果集是【1,2,3,4,5,6,8】
第八位 5×2,3×3,2×5，结果集【1,2,3,4,5,6,8,9】
第九位 5×2,4×3,2×5，结果集【1,2,3,4,5,6,8,9,10】
所以自己手动算了这么多步骤，规律应该可以看出来了，数字2，3，5分别在结果集中维护了一个指针，一开始都指向了索引0。结果集中第一位索引0上的值为1。
然后每次迭代找出2,3,5与索引位置上的值相乘的乘积中最小的一个，将这个结果放入结果集中的下一位，并将当前对应数字的指针位置沿着索引往后移动一位。如果有多个数与索引位置的乘积相等都为最小值，那么这些数字的指针都往后移动一位。
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int nthUglyNumber(int n) {
int[] res = new int[n];
res[0] = 1;
int p2 = 0, p3 = 0, p5 =0;
int k = 1;
while (k < n){
int num = Math.min(Math.min(res[p2]*2,res[p3]*3),res[p5]*5);
if (res[p2]*2==num){
p2++;
}
if (res[p3]*3==num){
p3++;
}
if (res[p5]*5==num){
p5++;
}
res[k] = num;
k++;
}
return res[k-1];
}
}
//leetcode submit region end(Prohibit modification and deletion)当前题目中固定了丑数范围为2,3,5，更多的非固定丑数范围的题目详见LeetCode刷题【313】 超级丑数
新更新内容：
重新做了LeetCode刷题【263】丑数，并再经过了前一段时间动态规划相关题目的练习之后，得到新的理解与启示
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int[] numArr = new int[]{2,3,5};
int[] pArr = new int[3];
for (int i = 1; i < n; i++) {
dp[i] = Math.min(Math.min(dp[pArr[0]]*numArr[0],dp[pArr[1]]*numArr[1]),dp[pArr[2]]*numArr[2]);
for (int p = 0; p < pArr.length; p++) {
if (dp[i] == dp[pArr[p]]*numArr[p]){
pArr[p] = pArr[p]+1;
}
}
}
return dp[n-1];
}
}代码可能大同小异，不过在理解上，
以一个现有的丑数序列为例[1,2,3,4,5,6,8,9,10,12]，一开始其实只有一个初始的索引0位置的1。根据丑数的特性，我们知道丑数F（n）一定能由之前的某个丑数乘以2或者乘以3或者乘以5得到，那么究竟取哪个呢，因为要保持递增性，所以应该是较小的。
而有了这个理解之后，在去看LeetCode刷题【313】 超级丑数的代码其实很容易从上面的新的代码能修改得到
发表评论