题目描述
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例：
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
思路
1.首先写出几个连续的丑数。
2.我们可以很容易的发现，状态转移方程为dp[i] = min(2dp[cnt2],3dp[cnt3],5*dp[cnt5])。
Java代码实现
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int ant2 = 0;
int ant3 = 0;
int ant5 = 0;
for(int i=1;i<n;i++){
dp[i] = Math.min(2*dp[ant2],Math.min(3*dp[ant3],5*dp[ant5]));
//一定要使用if if 而不是if else if，因为可能存在 2*dp[2] = 3*dp[1] = 6 代表的是同一个值，不应该将其放入结果集中
if(dp[i] == 2*dp[ant2])
ant2++;
if(dp[i] == 3*dp[ant3])
ant3++;
if(dp[i] == 5*dp[ant5])
ant5++;
}
return dp[n-1];
}
}
Golang代码实现
func nthUglyNumber(n int) int {
if n<=0{
return 0
}
dp := make([]int,n+1)
dp[1] = 1
ans2,ans3,ans5 := 1,1,1
for i:=2;i<=n;i++ {
min := dp[ans2]*2
if dp[ans3]*3 < min{
min = dp[ans3]*3
}
if dp[ans5]*5 < min{
min = dp[ans5]*5
}
dp[i] = min
if min == dp[ans2]*2{
ans2++
}
if min == dp[ans3]*3{
ans3++
}
if min == dp[ans5]*5{
ans5++
}
}
return dp[n]
}
