# \[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)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/duo-zhi-zhen/264-chou-shu-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.