# Ugly Number II

Ugly number is a number that only have factors 2, 3 and 5.

Design an algorithm to find the nth ugly number. The first 10 ugly numbers are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12...

## Example

If n=9, return 10.

## Solution

(1) DP O(n)

the key is there are 3 indexing as a jumper.

(2) Priority Queue O(klogk)

heapq.heappop , pop the min value int he queue.

while from 0 to N

while level < 3

push

这里让我们找到第n个丑陋数，还好题目中给了很多提示，基本上相当于告诉我们解法了，根据提示中的信息，我们知道丑陋数序列可以拆分为下面3个子列表：

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …

(2) 1×3, 2×3, 3×3, 4×3, 5×3, …

(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

(3) 解题思路：

参考：<http://www.geeksforgeeks.org/ugly-numbers/>

丑陋数序列可以拆分为下面3个子列表：

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …

(2) 1×3, 2×3, 3×3, 4×3, 5×3, …

(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

我们可以发现每一个子列表都是丑陋数本身(1, 2, 3, 4, 5, …) 乘以 2, 3, 5

接下来我们使用与归并排序相似的合并方法，从3个子列表中获取丑陋数。每一步我们从中选出最小的一个，然后向后移动一步。

<http://bookshadow.com/weblog/2015/08/19/leetcode-ugly-number-ii/>

```
class Solution:
    """
    @param {int} n an integer.
    @return {int} the nth prime number as description.
    """
    def nthUglyNumber(self, n):
        f = [0] * n
        f[0] = 1
        index2 = index3 = index5 = 0
        minValue = 0
        for i in range(1, n):
            f[i] = min(f[index2] * 2, f[index3] * 3, f[index5] * 5)
            if f[i] == f[index2] * 2 :
                index2 += 1
            if f[i] == f[index3] * 3 :
                index3 += 1
            if f[i] == f[index5] * 5 :
                index5 += 1
        return f[-1]

    def nthUglyNumber2(self, n):
        q = [1]
        i2 = i3 = i5 = 0
        while len(q) < n:
            m2, m3, m5 = q[i2] * 2, q[i3] * 3, q[i5] * 5
            m = min(m2, m3, m5)
            if m == m2:
                i2 += 1
            if m == m3:
                i3 += 1
            if m == m5:
                i5 += 1
            q += m,
        return q[-1]
```


---

# 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://liuxue2010.gitbook.io/data-structure-and-algorithms/data-structure/ugly-number-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.