154 - 264 丑数2

题目

编写一个程序，找出第 n 个丑数。

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

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1. 1 是丑数。

2. n 不超过1690。

解答

能想到的方法，就是不断除2，3，5，如果除光了就是丑数了。

https://leetcode-cn.com/problems/ugly-number-ii/solution/dui-he-dong-tai-gui-hua-by-powcai/

小顶堆

维护一个小顶堆，根就是最小值。因此每次把最小值拿出来，乘以2，3，5，就是丑数的可能性。

循环n遍拿的最小值，就是答案了

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        import heapq
        heap = [1]
        heapq.heapify(heap)
        res = 0
        for _ in range(n):
            res = heapq.heappop(heap)
            while heap and res == heap[0]:
                res = heapq.heappop(heap)
            a, b, c = res*2, res*3, res*5
            for t in [a, b, c]:
                heapq.heappush(heap, t)
        return res

Runtime: 244 ms, faster than 28.36% of Python3 online submissions for Ugly Number II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Ugly Number II.

动态规划

dp[i] = min(2 * dp[i2], 3 * dp[i3], 5 * dp[i5])

丑数是，2、3、5的倍数。即丑数=n个2*2+m个3*3+k个5*5。比如dp[1]= 2 = 1*2+0*3+0*5

我们要维护一个数组，里面是丑数从小到大排列，第n个值就是答案。

也就是说，在数组里的每个数，在未来数组里面都会被2、3、5乘一遍

于是我们就维护三个指针，分别指下一个还没被2乘、3乘、5乘的数。然后取最小值记录在dp里面

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        dp = [0]*n
        dp[0] = 1
        i2 = i3 = i5 = 0
        for i in range(1, n):
            dp[i] = min(2*dp[i2], 3*dp[i3], 5*dp[i5])
            if dp[i] == dp[i2]*2:
                i2 += 1
            if dp[i] == dp[i3]*3:
                i3 += 1
            if dp[i] == dp[i5]*5:
                i5 += 1
        return dp[-1]

Runtime: 156 ms, faster than 73.55% of Python3 online submissions for Ugly Number II.

Memory Usage: 12.8 MB, less than 100.00% of Python3 online submissions for Ugly Number II.

var nthUglyNumber = function(n) {
  const dp = new Array(n)
  dp[0] = 1
  let i2 = 0,
    i3 = 0,
    i5 = 0
  for (let i = 1; i < n; i++) {
    dp[i] = Math.min(2 * dp[i2], 3 * dp[i3], 5 * dp[i5])
    if (dp[i] === 2 * dp[i2]) {
      i2++
    }
    if (dp[i] === 3 * dp[i3]) {
      i3++
    }
    if (dp[i] === 5 * dp[i5]) {
      i5++
    }
  }
  return dp[n - 1]
};

Runtime: 68 ms, faster than 75.68% of JavaScript online submissions for Ugly Number II.

Memory Usage: 36.4 MB, less than 100.00% of JavaScript online submissions for Ugly Number II.

func min(a, b, c int) int {
    var m int
    if a < b {
        m = a
    } else {
        m = b
    }
    if c < m {
        return c
    } else {
        return m
    }
}
func nthUglyNumber(n int) int {
    dp := make([]int, n)
    dp[0] = 1
    var i2, i3, i5 int
    for i := 1; i < n; i++ {
        dp[i] = min(dp[i2]*2, dp[i3]*3, dp[i5]*5)
        if dp[i] == dp[i2]*2 {
            i2++
        }
        if dp[i] == dp[i3]*3 {
            i3++
        }
        if dp[i] == dp[i5]*5 {
            i5++
        }
    }
    return dp[n-1]
}

Runtime: 0 ms, faster than 100.00% of Go online submissions for Ugly Number II.

Memory Usage: 4.1 MB, less than 42.86% of Go online submissions for Ugly Number II.