1 题目及要求
1.1 题目描述
只包含因子2、3和5的数称为丑数（Ugly Number），习惯上我们把1当做第一个丑数。求按从小到大顺序的第n（n > 0）个丑数。
2 解答
2.1 代码
bool isUgly(int n){
while(!(n%2)) n /= 2;
while(!(n%3)) n /= 3;
while(!(n%5)) n /= 5;
return n==1;
}
// 方案1
int getUglyNumber1(int index){
if(index < 1) return 0;
int n(0);
while(index){
++n;
if(isUgly(n)) --index;
}
return n;
}
// 方案2, 需要额外空间,时间效率较高
int getUglyNumber2(int index){
if(index < 1) return 0;
int *pn = new int[index];
pn[0] = 1;
for(int k1(1),k2(0),k3(0),k5(0);k1<index;++k1){
pn[k1] = min(2*pn[k2], min(3*pn[k3], 5*pn[k5]));
while(2*pn[k2]<=pn[k1]) ++k2;
while(3*pn[k3]<=pn[k1]) ++k3;
while(5*pn[k5]<=pn[k1]) ++k5;
}
index = pn[index-1];
delete[] pn;
return index;
}
