題目

給你一個(gè)整數(shù) n ，請你找出并返回第 n 個(gè) 丑數(shù) 。

丑數(shù) 就是只包含質(zhì)因數(shù) 2、3 和/或 5 的正整數(shù)。

示例 1：

輸入：n = 10
輸出：12
解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個(gè)丑數(shù)組成的序列。
示例 2：

輸入：n = 1
輸出：1
解釋：1 通常被視為丑數(shù)。

代碼

func nthUglyNumber(n int) int {
    dp := make([]int,n)
    dp[0]=1
    p2,p3,p5:=0,0,0
    var p *int
    for i:=1;i<n;i++{
        v := dp[p2]*2
        p = &p2
        if v > dp[p3]*3{
            v=dp[p3]*3
            p = &p3
        }
        if v > dp[p5]*5{
            v = dp[p5]*5
            p = &p5
        }
       
        *p++
        if v > dp[i-1]{
            dp[i]=v
        }else{
            i--
        }
    }
   
    return dp[n-1]
}