264 丑数2-中等

题目：

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是质因子只包含 2、3 和 5 的正整数。

分析：

所谓丑数，就是说该数字只能是 2，3，5 的倍数。

一个丑数乘以 2 或者 3 或者 5 ，结果还是丑数，要选最小的那个。

所以，需要维护三个指针，p1,p2,p3, 分别表示下一个丑数是当前指针所指向的丑数乘以不同的质因子得来。

一旦被使用，说明该指针所指向的丑数 乘以 指针所代表的质因子，就是当前下一个（最小的）的丑数。

该指针递增，从以往的丑数序列中选最小的丑数作为该质因子新的基数。

所以指针加一。

===

这里可以这样理解：p1,p2,p3 分别表示质因子2,3,5所选以往丑数作为基数的索引。该索引保证该质子下，选最小的那个。

起初，p1,p2,p3 都是从 1（丑数） 作为基数开始。

随着丑数的产生，丑数序列中肯定越靠前的越小。一旦被使用，只能选下一个较小的。

// date 2023/11/09
func nthUglyNumber(n int) int {
    if n < 1 { return 1 }
    dp := make([]int, n)
    dp[0] = 1
    p1, p2, p3 := 0, 0, 0
    for i := 1; i < n; i++ {
        dp[i] = min(2 * dp[p1], min(3 * dp[p2], 5 * dp[p3]))
        if dp[i] == 2 * dp[p1] { p1++ }
        if dp[i] == 3 * dp[p2] { p2++ }
        if dp[i] == 5 * dp[p3] { p3++ }
    }
    return dp[n-1]
}

func min(x, y int) int {
    if x < y { return x }
    return y
}