一、题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
二、思路讲解
首先可以想到，所有的丑数都是由前面的丑数乘上2、3或5得来的。而我们需要有顺序的丑数序列，就有必要知道，前面的数乘上2、3或5之后的数谁大谁小。因此，我们可以设置三个指针a、b、c；指针a表示所指的数还没有乘2，指针b表示所指的数还没有乘3，指针c表示所指的数还没有乘5。那么下一个丑数就应该是min{dp[a]*2, dp[b]*3, dp[c]*5}，然后对应的指针后移。比如说，如果最小的值为dp[a]*2，那么下一个丑数就是dp[a]*2，那么a指针就后移（移到没有乘过2的数上面，也就是下一个数），然后dp[i-1]即为第i个丑数。
三、Java代码实现
class Solution { public int nthUglyNumber(int n) { int []dp = new int[2000]; dp[0] = 1; int a=0, b=0, c=0; int count = 1; while(count <= n){ int temp = Math.min(Math.min(dp[a]*2, dp[b]*3), dp[c]*5); dp[count++] = temp; //这里需要特别注意，有可能出现该丑数既等于dp[a]*2又等于dp[b]*3的情况 //此时a指针和b指针都应该后移，所以不能写成else if，必须是三个if if(temp == dp[a]*2){ a++; } if(temp == dp[b]*3){ b++; } if(temp == dp[c]*5){ c++; } } return dp[n-1]; } }
四、时空复杂度分析
时间复杂度： O(N) 需要遍历dp数组
空间复杂度： O(N) 需要一个dp数组
