因为丑数只含素因子2，3，5。所以 任一丑数 = 2或3或5 * 更小的丑数（因为丑数素因子只由2 3 5组成,所以分解出了一个2或3或5，剩下部分仍是丑数）
所以用2 3 5 * 其他丑数，可以求得所有丑数
假如an是丑数数列，那丑数的全集就是
2a1 2a2 ... 2*an
3a1 3a2 ... 2*an
5a1 5a2 ... 2*an
我们把1作为丑数的第一项a1
不难看出这是一个 从左到右从上到下递增 的二维数组。我们可以把每行的第一个 (2*a1,3*a1,5*a1) 进行比较,然后选出其最小值(2*a1),就是第二项。然后把刚刚选出最小值那行的下一个(2*a2)以及刚刚没被选上的数(3*a1,5*a2)进行比较得出第三项.以此类推...
需要注意的是因为有可能出现值相等的情况(2*a3(2*3) 和 3*a2(3*2))，这个时候需要把都为最小值的行都推到下一个.(2*a3 和 3*a2 下一轮变成 2*a4 和 3*a3)。
代码:
public int nthUglyNumber(int n) {
int[] r = new int[n];
r[0] = 1;
//分别是 2 3 5 乘到了第几项
int t2 = 0,t3 = 0,t5 = 0;
int i = 1;
while (i < n){
r[i] = Math.min(2*r[t2],Math.min(3*r[t3],5*r[t5]));
// 2那行被选 t2移到下一项
if(2*r[t2] == r[i]) ++t2;
if(3*r[t3] == r[i]) ++t3;
if(5*r[t5] == r[i]) ++t5;
++i;
}
return r[n-1];
}
