丑数（java）

题目描述：

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

分析：

最开始写了个从1开始判断自然数是否是丑数，直到找到第n个丑数为止。这个方法显然耗时很久。（判断一个数是否是丑数的思路：如果一个数能被2整除，我们把它连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就除以5.如果最后我们得到的是1，那么这个数就是丑数，否则不是。）

思路：
只包含因子2,3，5的数称为丑数，也就是说一个丑数肯定是某个丑数乘以2,3,5的结果。用一个数组保存已有的丑数，然后计算后面的丑数。（牺牲空间，以换取时间）
这种方法的关键在于排序，每个丑数都是由别的丑数乘2/3/5来的，所以把所有的丑数存储，记住前面的下标，一旦前面那个数的乘2/3/5的丑数已经被后边使用，就把相应的下标向前移动一个。

解答：

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<=6) return index;
        int i2 =0,i3=0,i5=0;
        int[] dp = new int[index];
        dp[0]=1;
        for(int i=1;i<index;i++) {
            dp[i] = Math.min(dp[i2]*2,Math.min(dp[i3]*3,dp[i5]*5));//其中最小的为下一个丑数
            //把已经存在的数，往前移动一下
            if(dp[i]==dp[i2]*2) i2++;
            if(dp[i]==dp[i3]*3) i3++;
            if(dp[i]==dp[i5]*5) i5++;
        }
        return dp[index - 1];
    }
}

运行结果

始终相信，在线编程题目考的就是你的逻辑思维，不可能要你写上一大堆的代码，所以代码一定是越简洁越好。