设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例
样例 1：
输入：9
输出：10
样例 2：
输入：1
输出：1
挑战
要求时间复杂度为 O(nlogn) 或者 O(n)。
注意事项
我们可以认为 1 也是一个丑数
class Solution {
public:
/**
* @param n: An integer
* @return: return a integer as description.
*/
int nthUglyNumber(int n) {
// write your code here
int* res=new int[n];
res[0]=1;
int two=0;
int three=0;
int five=0;
for(int i=1;i<n;i++){
// res[i]=Math.min(res[two]*2,res[three]*3,res[five]*5);
if(res[two]*2<res[three]*3){
res[i]=res[two]*2;
}else{
res[i]=res[three]*3;
}
if(res[i]>res[five]*5){
res[i]=res[five]*5;
}
if(res[i]==res[two]*2)
two++;
if(res[i]==res[three]*3)
three++;
if(res[i]==res[five]*5)
five++;
}
return res[n-1];
}
};
算法设计思想：
- 创建三个动态下标充当动态指针，并初始指向初始位；
- 当对应的下标的值是最小的时候，对应的下标往前一步；
