49剑指OFFER之丑数

参考资料：
[1]代码参考 anybody的回答：
https://www.nowcoder.com/profile/5810633/codeBookDetail?submissionId=16629921

[2]代码思路：
https://www.cnblogs.com/lfeng1205/p/6932328.html

即可解决丑数的问题。常规代码时间超时：

//代码运行超时
    int GetUglyNumber_Solution(int index) {
    
        if(index<0)
            return 0;
        int uglyNumberFound = 0;
        int number = 0;
        while(uglyNumberFound <index)
        {
            ++number;
            if(IsUgly(number))//如果是丑数的话，加1.
                ++uglyNumberFound;
            
        }
        return number;
        
    }
    
    bool IsUgly(int number)
    {
        while(number%2 == 0)//能被2整除就连续除以2
            number/=2;
        while(number%3 ==0)//能被3整除就连续除以3
            number/=3;
        while(number%5 ==0)//能被5整除就连续除以5
            number/=5;
        if(number ==1)
            return true;
        else
            return false;
    }

合格的程序如下：

class Solution {
public:
     int GetUglyNumber_Solution(int index) {
         //步骤0：定义一个丑数集合,怎么确保丑数是排好序的呢？如下。
         if(index<7)
             return index;
         //只能用小括号啊！！！！！
         vector<int> res(index);
         res[0] = 1;
         int t2 = 0,t3 =0,t5 = 0;
         //int i = 1 !!!!
         for(int i=1;i<index;i++)
         {
             //步骤1：在已有的丑数中乘以2，乘以3，乘以5，然后选择最小的丑数
             res[i]=min(res[t2]*2,min(res[t3]*3,res[t5]*5));//min()啊
             //步骤2：为了防止重复，如最小丑数乘等于2的丑数，那么t2++;
             //如最小丑数乘等于3的丑数，那么t3++;
             //如最小丑数乘等于5的丑数，那么t5++;
             if(res[i] == res[t2]*2) t2++;
             if(res[i] == res[t3]*3) t3++;
             if(res[i] == res[t5]*5) t5++;
         }
         return res[index-1];
    }
};