把只包含质因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,但14不是,因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
有了上面的定义我们就可以知道,丑数的形式就是图片说明
所以我们可以定义一个数组,存储第n个丑数。
因为我们要将丑数按从小到大的顺序排序,所以我们就得将对应的丑数放在对应的下标位置,小的放前面。
因为最小的丑数就是1,所以我们初始化dp[0]=1,那么接下来的一个丑数是什么呢?我们自己知道是2。
但是我们能不能有一个格式,去将得到接下来的丑数是谁呢?
这个时候上面我们的出来的丑数的格式就起作用了,丑数的形式无非就是这样图片说明
所以我们就将dp[n]去乘以 2、3、5,然后比较出最小的那个,就是我们当前小的那个丑数了。
下面代码实战看注释(自己演示一遍就明白其中的道理)

public int GetUglyNumber_Solution(int index) {
        //1 2 3 4 5 6 8
        if(index <= 6)
            return index;
        int i2 = 0,i3 = 0,i5 = 0;  /*三个指针,记录乘2、3、5的次数*/
        int[] dp = new int[index];  /*存放丑数*/
        dp[0] = 1;  /*第一个丑数是1*/

        for(int i = 1; i < index; i++){
            dp[i] = Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));  
            /*第一次是 2、3、5比较,得到最小的是2*/
            /*第二次是 4、3、5比较,为什么是4了呢?因为上次2已经乘了一次了,可以放的丑数在4、3、5之间,我们知道是3*/
            if(dp[i] == dp[i2]*2)
                i2++;   /*2被乘了一次了,i2加1*/
            if(dp[i] == dp[i3]*3)
                i3++;  /*3被乘了一次,i3加1*/
            if(dp[i] == dp[i5]*5)
                i5++;
        }
        return dp[index-1];
    }