设计一个算法，找出只含素因子2，3，5 的第 n 小的数。
符合条件的数如：1, 2, 3, 4, 5, 6, 8, 9, 10, 12...
样例
如果n = 9， 返回10

暴力遍历

暴力遍历，判断一个数是否只有2，3，5的素因子，如果是，放入容器，计数加1，直到找到第n个然后输出就行了，写起来也简单：

bool IsUgly(int n)
    {
        while(n%2==0)   //可以被2整除的话就除以2，下同
        {
            n/=2;
        }
         while(n%3==0)  
        {
            n/=3;
        }
         while(n%5==0)   
        {
            n/=5;
        }
        if(n==1)   //如果最后除完得到的是1，说明确实只含有2，3，5的因子，则是丑数
        return true;
        else 
        return false;
    }
    int nthUglyNumber(int n)
    {
        int num=1;   //从1开始遍历 
        int index=0;  //记录已找到丑数的个数
        while(1)
        {
            if(IsUgly(num))  index++;  //如果是丑数，那么计数器加1
            if(index==n)  return num;   //如果是第n个，那么就返回
            num++;                      
        }
    }

不出意料大数据的时候时间会超出限制。

找规律

这种题说起来都是数学题，只要能找出规律来就能减少运算量。
注意到这样一个现象:一个丑数乘以2，3，5的话肯定还是丑数，也就是说丑数可以由丑数生成，我们如果只有一个初始值1，那么还是可以生成丑数。我们把丑数序列记作res.
第二个丑数应该是： min(res[1]*2,res[1]*3,res[1]*5); min(2,3,5)=2
第三个丑数应该是： min(res[2]*2,res[1]*3,res[1]*5); min(4,3,5)=3
第三个丑数应该是： min(res[2]*2,res[2]*3,res[1]*5); min(4,6,5)=4

每次更新只更新一个数十为了保证这样更新的数一定是有序的，我们用了三个指针在这里，2，3，5这三个因子保持不动，哪一个因子作用的数被采纳，我们就把对应的指针+1，移到下一个数上，这样虽然会有重复计算（因为一般情况下我们每次都只更新一个指针），但是可以保证每次更新的都是最小的丑数。如果一个循环中算出了两个最小值，那么对应的两个指针都++，下面是当n等于9的时候的打印日志：

打印日志

int nthUglyNumber(int n) {
        int start=1;
     
        vector<int> res;      //存放结果
        res.push_back(start);   //第一个数先放进去
        if(n==1)    //处理特殊情况
        return 1;
        int index=1;   //序列号
        int p2,p3,p5;   //记录的是当前乘以2，3，5的数的索引。
        p2=p3=p5=0;   //所以初始化为1，每次枚举三个数
        while(index<n)
        {
            res.push_back(min3(2*res[p2],3*res[p3],5*res[p5]));   //每次把最小的放入数组
            cout<<2*res[p2]<<" "<<3*res[p3]<<" "<<5*res[p5]<<endl;
            if(2*res[p2]==*(res.end()-1))   p2++;   
            //如果刚放入的是2*res[p2],就把p2++,下次就用下一个数乘以2了。
            if(3*res[p3]==*(res.end()-1))   p3++; 
            if(5*res[p5]==*(res.end()-1))   p5++; 
            //上面三个if之间不要用else，因为可能存在多个最小值，都需加1。
            index++;            //索引加1，
        }
        return *(res.end()-1);   //返回最后一个数
        // write your code here
    }

利用set暴力去重排序。

这样也是可以的，不过计算量也是挺大的，因为还是有大量的重复计算。我就不写了。