49.丑数（中等）

考点：本题考查时间空间效率的平衡

题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路一：暴力法

逐个判断每个整数是不是丑数，结果运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大

public class Solution {
  
    public int GetUglyNumber_Solution(int index) {//按照顺序判断每个整数是不是丑数
        if(index<=0)
            return 0 ;
        int num = 0;
        int ugly = 0;
        while(ugly<index){
            num++;
            if(IsUgly(num)){
                ugly++;
            }
        }
        return num;
    }
    private boolean IsUgly(int num){//判断一个数是不是丑数
        while(num%2==0)
            num/=2;
        while(num%3==0)
            num/=3;
        while(num%5==0)
            num/=5;
        return(num==1)? true:false;
    }
}

思路二：创建数组保存已经找到的丑数，用空间换时间

根据丑数的定义，丑数应该是另一个丑数乘以2,3或者5的结果（1除外）。因此，可以创建一个数组，里边的数字是排好序的丑数，每个丑数都是前面的丑数乘以2,3或者5得到的。
难点在于如何确保数组里的丑数是排好序的。
用三个指针来记录当前乘以2、乘以3、乘以5的最小值，然后当其被选为新的最小值后，要把相应的指针+1。因为这个指针会逐渐遍历整个数组，因此最终数组中的每一个值都会在需要的时候乘以2、3、5。

//求按从小到大的顺序的第N个丑数
public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=0) return 0;
        int[] result = new int[index];
        result[0] = 1;
        ///初始化三个指向三个潜在成为最小丑数的位置
        int i = 0 ;
        int j = 0 ;
        int k = 0 ;
        for(int p=1;p<index;p++){//循环index-1次
            result[p] = Math.min(result[i]*2,Math.min(result[j]*3,result[k]*5)); //找出三个数里面的最小值
            if(result[i]*2==result[p]) i++;
            if(result[j]*3==result[p]) j++;
            if(result[k]*5==result[p]) k++;
        }
        return result[index-1];
        
    }
}

两种思路相比较，第二种思路不需要在非丑数的整数上进行任何计算，提升了时间效率，但是需要用一个数组保存已经生成的丑数，增加了空间消耗。第二种思路就是用较小的空间消耗换取了时间效率的提升。