//思路：第一步：判断一个数是否为丑数。由于丑数是只包好2，3，5的因子的数,因此我们自然就想到了判断一个丑数先对2进行求余数如果为0再对它进行求除数减小数的大小，

//同样对3，和5也一样，最后如果结果为1就返回true。第二步，通过判断是否为丑数来数出第N个丑数对应的值。

public class FindUglyNumber {

    //判断一个数是不是丑数

    public boolean isUgly(int number){

        if(number<=0)

            return false;

        while(number%2==0)

            number/=2;

        while(number%3==0)

            number/=3;

        while(number%5==0)

            number/=5;

        return (number==1)?true:false;

    }

    public int uglyNumber(int uglyNumber){

        if(uglyNumber<=0)

            return 0;

        int ugly=0;//记录丑数的个数

        int number=0;//记录数字

        while(ugly<uglyNumber){

            number++;

            if(isUgly(number))

                ugly++;

        }

        return number;

    }

    public static void main(String[] args){

        FindUglyNumber findUglyNumber=new FindUglyNumber();

        int uglyNumber=findUglyNumber.uglyNumber(3);

        System.out.println(uglyNumber);

    }

}

//思路:将uglyNumber按照从小到大的顺序保存在数组中。因为uglyNumber是只包含2，3，5因子的数，

//因此可以用一个M表示数组中最大的数，也是数组中最后一个存入的数，而将之前的丑数分别乘2，3，5，然后保留大于M值的最小数。

//作为下一个M。我们前面说，M之前的每一个丑数都乘以2，3，5，其实这个可以确定在乘以2时在一定存在某个值，在它之前的数都小于M

//在它之后的数都大于M。

public class FindUglyNumber1 {

   public int findUglyNumer(int index){

       int[] uglyNumber=new int[index];

       uglyNumber[0]=1;

       int nextNumber=1;

       int nextNumber2=0;

       int nextNumber3=0;

       int nextNumber5=0;

       while(nextNumber<index){

           int min=min(uglyNumber[nextNumber2]*2,uglyNumber[nextNumber3]*3,uglyNumber[nextNumber5]*5);

           uglyNumber[nextNumber]=min;

           while(uglyNumber[nextNumber2]*2<=uglyNumber[nextNumber])

               nextNumber2++;

           while(uglyNumber[nextNumber3]*3<=uglyNumber[nextNumber])

               nextNumber3++;

           while(uglyNumber[nextNumber5]*5<=uglyNumber[nextNumber])

               nextNumber5++;

           nextNumber++;

       }

       int ugly=uglyNumber[nextNumber-1];

       return ugly;

   }

public int min(int i, int j, int k) {

    int min=i<j?i:j;

    return min<k?min:k;

}

public static void main(String[] args){

    FindUglyNumber1 findUglyNumber=new FindUglyNumber1();

    int uglyNumber=findUglyNumber.findUglyNumer(3);

    System.out.println(uglyNumber);

}

}