原理：
大丑数=小丑数x丑数因子（2，3，5）
所有丑数的集合，必然是由这三个数组合并去重得到的：
A：{1*2，2*2，3*2，4*2，5*2，6*2，8*2，10*2......}
B：{1*3，2*3，3*3，4*3，5*3，6*3，8*3，10*3......}
C：{1*5，2*5，3*5，4*5，5*5，6*5，8*5，10*5......}
这就将求丑数问题转换成了三个有序数组的无重复元素合并的问题。
思路：
合并有序数组，可以让每个数组都对应一个指针，然后比较这些指针所指的数中哪个最小，就将这个数放到结果数组中，然后该指针向后挪一位。
为了去重，如果多个元素都是最小，那么这多个指针都要往后移动一个。(不用 if，else 的原因)
代码如下：
时间复杂度O（n），空间复杂度O（n）
class Solution { public int nthUglyNumber(int n) { int a = 0, b = 0, c = 0; int[] dp = new int[n]; dp[0] = 1; int n2,n3,n5; for (int i = 1; i < n;i++){ n2 = dp[a]*2; n3 = dp[b]*3; n5 = dp[c]*5; dp[i] = Math.min(Math.min(n2, n3), n5); if (dp[i] == n2) a++; if (dp[i] == n3) b++; if (dp[i] == n5) c++; } return dp[n-1];//第n个数在数组中为第n-1个元素 } }
原文：https://www.cnblogs.com/zccfrancis/p/14446939.html