4. 丑数 II

设计一个算法，找出只含素因子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];
        
    }
};

算法设计思想：

• 创建三个动态下标充当动态指针，并初始指向初始位；
• 当对应的下标的值是最小的时候，对应的下标往前一步；

参考链接:https://www.bilibili.com/video/BV1gz411v7C5?t=371