题目描述
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
思路
1.首先写出几个连续的丑数。
2.我们可以很容易的推导出状态转移方程为：dp[i] = min(2dp[cnt2],3dp[cnt3],5*dp[cnt5])。
Java代码实现
public class Solution {
public int GetUglyNumber_Solution(int index) {
if(index <= 0){
return 0;
}
int[] dp = new int[index+1];
dp[1]=1;
int ans2= 1,ans3= 1,ans5 = 1;
for (int i = 2; i <= index; i++) {
dp[i] = Math.min(dp[ans2]*2,Math.min(dp[ans3]*3,dp[ans5]*5));
if(dp[i] == dp[ans2]*2){
ans2++;
}
//一定要使用if if 而不是if else if，因为可能存在 2*dp[2] = 3*dp[1] = 6 代表的是同一个值，不应该将其重复放入结果集中
if(dp[i] == dp[ans3]*3){
ans3++;
}
if(dp[i] == dp[ans5]*5){
ans5++;
}
}
return dp[index];
}
}
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]
}
