丑数

题目描述

把只包含质因子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]
}