> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/8.data-structure/4ugly-number-ii.md).

# 4.Ugly Number II

## 1.Description(Medium)

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

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

### Notice

Note that`1`is typically treated as an ugly number.

**Example**

If`n=9`, return`10`.

[**Challenge**](https://www.lintcode.com/en/problem/ugly-number-ii/#challenge)

O(*nlogn*) or O(*n*) time.

[**Tags**](https://www.lintcode.com/en/problem/ugly-number-ii/#tags)

[LintCode Copyright](https://www.lintcode.com/tag/lintcode-copyright/) [Priority Queue](https://www.lintcode.com/tag/priority-queue/)

## 2.Code

这就是多链表Merge Sort的一个扩展题。对于任意一个ugly number - K, 2\*K, 3\*K, 和5\*K都是ugly number，所以说新的ugly number都是从已有的ugly number上，通过与{2,3,5}相乘而产生的。

![](/files/-M33gzK0u30IH5bvQr_v)都是ugly number。只要不断把新产生的ugly number通过merge sort添加到原有的ugly number数组中就可以了，直到找到第N个。

```
 public int nthUglyNumber(int n) {

        ArrayList<Integer> list=new ArrayList<Integer>();
        list.add(1);
        int i2=0;
        int i3=0;
        int i5=0;
        while(list.size()<n){
            int m2=list.get(i2)*2;
            int m3=list.get(i3)*3;
            int m5=list.get(i5)*5;

            int min=Math.min(m2, Math.min(m3, m5));
            list.add(min);
            if(min==m2) i2++;
            if(min==m3) i3++;
            if(min==m5) i5++;

        }

        return list.get(list.size()-1);       
    }
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## 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://junnie.gitbook.io/nine-chapter/8.data-structure/4ugly-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.