JZ33：丑数

//-----------运行超时-------------https://www.jianshu.com/p/a56fc45c1c9a-----------
    //所谓一个数m是另一个数n的因子，是指n能被m整除，也就是说n%m==0.
    //根据丑数的定义，丑数只能被2，3，5整除。也就是说如果一个数能被2整除，我们把它连续除以2；
    //如果能被3整除，就连续除以3；如果能被5整除，就除以5.如果最后我们得到的是1，那么这个数就是丑数，否则不是。
    public static boolean isUgly(int number){
        while(number%2==0)
            number/=2;
        while(number%3==0)
            number/=3;
        while(number%5==0)
            number/=5;
        return number==1 ? true : false;
    }
    public static int getUglyNumber(int index){
        if(index<=0){
            return 0;
        }
        int number=0;
        int UglyFound=0;
        while(UglyFound<index){
            number++;
            if(isUgly(number)){
                ++UglyFound;
            }
        }
        return number;
    }

//https://blog.csdn.net/wszy1301/article/details/80910626
    public static int GetUglyNumber_Solution(int index){
        if(index<=0){
            return 0;
        }
        int[] res=new int[index];
        res[0]=1;//先把1放入
        int m2=0;//制乘以2的位置，假设得到一个丑数是乘以2得到的，那么下一次就是数组中的下一个丑数可能达到。
        int m3=0;
        int m5=0;
        for(int i=1;i<index;i++){
            int min=Math.min(res[m2]*2, Math.min(res[m3]*3,res[m5]*5));
            res[i]=min;
            if(min==res[m2]*2){
                              //假设res[1]是乘以2得到的丑数，那么下一次就要判断
                               //是否是res[2]乘以2可能得到丑数，所以就要++
                m2++;
            }
            if(min==res[m3]*3){
                m3++;
            }
            if(min==res[m5]*5){
                m5++;
            }
        }
        return res[index-1];
    }