问题：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
分析：
（1）N<7，直接返回N，因为（1-6）内的第N个丑数，就是本身。
（2）正常情况：使用一个数组dp[ ] 记录找到的丑数升序序列.
（3）序列构建过程：初始化序列dp[0]为1，设置记录器i（记录构建长度）；在逻辑上将序列分为三个子序列，设t2为以2为倍数的子序列的哨兵，它表示t2记录的当前位置即将进行dp[t2]*2，同理设置t3，t5；在dp[i]实例化之前,先分别计算dp[t?]*?(?=2/3/5)，然后三者比较取小（保证升序），在保存了确定的子序列的计算结果后，哨兵+1.
（4）结束条件：i ==N
code：
//别人的代码:解决思路类似于动态规划 public int GetUglyNumber_Solution(int index) { if(index<7) { return index; } int[] dp = new int[index]; dp[0] = 1; int t2=0,t3=0,t5=0; for(int i=1;i<index;i++) { dp[i] = Math.min(dp[t2]*2, Math.min(dp[t3]*3, dp[t5]*5)); if(dp[i]==dp[t2]*2)t2++; if(dp[i]==dp[t3]*3)t3++; if(dp[i]==dp[t5]*5)t5++; } //System.out.println(Arrays.toString(dp)); return dp[index-1]; }
参考代码：
链接：https://www.nowcoder.com/questionTerminal/6aa9e04fc3794f68acf8778237ba065b?f=discussion 来源：牛客网 class Solution { public://别人的代码就是精简，惭愧啊，继续学习。 int GetUglyNumber_Solution(int index) { if (index < 7)return index; vector<int> res(index); res[0] = 1; int t2 = 0, t3 = 0, t5 = 0, i; for (i = 1; i < index; ++i) { res[i] = min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5)); if (res[i] == res[t2] * 2)t2++; if (res[i] == res[t3] * 3)t3++; if (res[i] == res[t5] * 5)t5++; } return res[index - 1]; } };
原文：https://www.cnblogs.com/dream-flying/p/12904262.html