丑数

1.题目
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
如，输入7，返回8
2.思路
方法一：个人感觉思路对的，可是牛客说我时间复杂度过大,但是代码比较直观
所谓一个数m是另一个数n的因子，是指n能被m整除，也就是说n%m==0.

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        int[] result = new int[index];
        result[0]=1;
        int count=1;
        int calNum=1;
        while(count<index){
            calNum++;
            if(isUglyNum(calNum)){
               result[count] = calNum;
                count++;
            }
        }
        return result[index-1];
    }
        /**
     * 判断一个数是否是丑数，即只包含因子2，3，5的数，即
     * 如果可以被2整除，就连续除以2，直到不能被2整除为止
     * 如果可以被3整除，就连续除以3，直到不能被3整除为止
     * 如果可以被5整除，就连续除以5，直到不能被5整除为止
     * 如果最后的结果是1，说明是丑数，否则不是
     * 例如，30，可以被2整除，然后除以2得到15
     *      15，可以被3整除，然后除以3得到5
     *      5，可以被5整除，然后除以5得到1
     */
     boolean isUglyNum(int num){
        while(num%2==0){
            num=num/2;
        }
        while(num%3==0){
            num=num/3;
        }
        while(num%5==0){
            num=num/5;
        }
        return num==1?true:false;
    }
}

方法二： 以空间换时间
首先，每个丑数=2^x+3^y+5^z，那么请看下图：

看了好多题解，都没看懂，特意画了个图，一下子就明白了！

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index==0) return 0;
        int p2=0;//队列1
        int p3=0;//队列2
        int p5=0;//队列3
        int[] uglyArr=new int[index];//存储丑数
        uglyArr[0]=1;
        for(int i=1;i<index;i++){
            uglyArr[i]=Math.min(uglyArr[p2]*2,Math.min(uglyArr[p3]*3,uglyArr[p5]*5));//选取每一行中最小的丑数
            if(uglyArr[i]==uglyArr[p2]*2) p2++;//加1，且去重复
            if(uglyArr[i]==uglyArr[p3]*3) p3++;
            if(uglyArr[i]==uglyArr[p5]*5) p5++;
        }
        return uglyArr[index-1];
    }
}