# \[264]\[中等]\[动态规划]\[三指针]\[堆] 丑数 II

## 题目描述

[264. 丑数 II](https://leetcode-cn.com/problems/ugly-number-ii/) [剑指 Offer 49. 丑数](https://leetcode-cn.com/problems/chou-shu-lcof/)

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

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

示例:

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

说明:

* 1 是丑数。
* n 不超过1690。

## 解题思路

[丑数 II](https://leetcode-cn.com/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode/)

对于很多限制了**数值范围**或**数量大小**的数学题目, 常常先将范围内所有的结果计算出来, 缓存起来, 之后对于每一个用例, 直接查询答案即可.

由于本题中指定查询的丑数数量不大于1690, 因此首先计算出来这1690个丑数是什么, 然后直接返回对应位置的数值即可.

### 三指针+动态规划

本题的动态规划的形式有些特别, 可以把最终丑数的列表作为状态, 即第$$i$$个丑数是什么. 状态转移方程也需要借助**三指针**才能给出.

从`1`开始, 我们不断地乘上`2`, `3`, `5`, 这样得到数, 它的因子中肯定只有`2`, `3`, `5`这三个正整数, 剩下的就是控制顺序, 依次得到递增的丑数, 保证顺序的排列.

使用三个指针$$i\_2$$, $$i\_3$$, $$i\_5$$, 指向已有的丑数列表中的位置, 该位置乘以这个指针代表的因子, 就得到了新的丑数. 对于新的丑数, 一定是前面比较小的丑数乘以三个因子得到的, 我们选取$$2 \times nums\[i\_2]$$, $$3 \times nums\[i\_3]$$, $$5 \times nums\[i\_5]$$中最小的丑数添加到丑数列表中, 作为新的丑数, 并将对应因子的指针前进一位.

状态转移方程可以记为:

$$nums\[j] = \min(2 \times nums\[i\_2], 3 \times nums\[i\_3], 5 \times nums\[i\_5])$$

可以看到$$j$$和$$i\_\*$$, 两个下标虽然作用于同一个数组, 但意义不同, 这点是需要注意的.

为什么新的丑数一定在$$2 \times nums\[i\_2]$$, $$3 \times nums\[i\_3]$$, $$5 \times nums\[i\_5]$$之中, 因为三个指针指示的位置之前的数字, 都分别已经和对应的因子乘过了, 得到的值已经被添加到丑数列表中了(每次循环只有被添加值对应因子的指针左移一位, 其他两个指针保持不变). 因此新的丑数一定在这三个中出现.

```python
class Ugly:
    def __init__(self):
        self.cache = [1]
        p2, p3, p5 = 0, 0, 0
        for i in range(1690):
            res2, res3, res5 = self.cache[p2] * 2, self.cache[p3] * 3, self.cache[p5] * 5
            new_number = min([res2, res3, res5])
            self.cache.append(new_number)

            p2 = p2 + 1 if new_number == res2 else p2
            p3 = p3 + 1 if new_number == res3 else p3
            p5 = p5 + 1 if new_number == res5 else p5


class Solution:
    ugly = Ugly()
    def nthUglyNumber(self, n: int) -> int:
        return self.ugly.cache[n - 1]
```

### 堆

堆的方法与上面三指针的方法在思路上类似, 都是不断的乘上`2`, `3`, `5`, 但控制下一个丑数的任务简化了, 由三指针交给了擅长存储和排序的堆这种数据结构. 将所有计算得到的丑数都放入堆中, 这里使用最小堆. 每次取堆顶的元素加入到丑数列表中, 这个数肯定是当前未加入到丑数列表中的最小数.

需要注意堆中数字重复的问题, 为此需要额外使用一个哈希表来存储已经在列表中的丑数.

```python
class Ugly:
    def __init__(self):
        self.cache = []
        heap = [1]
        heapq.heapify(heap)
        seen = set([1])

        for _ in range(1690):
            t_ugly = heapq.heappop(heap)
            self.cache.append(t_ugly)
            for i in [2, 3, 5]:
                new_ugly = t_ugly * i
                if new_ugly not in seen:
                    heapq.heappush(heap, new_ugly)
                    seen.add(new_ugly)


class Solution:
    ugly = Ugly()
    def nthUglyNumber(self, n: int) -> int:
        return self.ugly.cache[n - 1]
```

## 相关题目

* [\[313\]\[中等\]\[堆\] 超级丑数](https://blessbingo.gitbook.io/garnet/suan-fa/dui/313-chao-ji-chou-shu)