---
# System prepended metadata

title: 264. Ugly Number II
tags: [pointer, Leetcode, medium, python, array, c++]

---

###### tags: `Leetcode` `medium` `pointer` `array` `python` `c++`

# 264. Ugly Number II

## [題目連結:] https://leetcode.com/problems/ugly-number-ii/description/

## 題目:
An **ugly number** is a positive integer whose prime factors are limited to ```2```, ```3```, and ```5```.

Given an integer ```n```, return the ```nth``` **ugly number**.

**Example 1:**
```
Input: n = 10
Output: 12
Explanation: [1, 2, 3, 4, 5, 6, 8, 9, 10, 12] is the sequence of the first 10 ugly numbers.
```
**Example 2:**
```
Input: n = 1
Output: 1
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
```

## 解題想法:
* 此題為求第n個ugly number:
    * 其因數只能為2,3,5構成
* 指針判斷:
    * 初始nums=[1] 
    * 用3個pointer維護，初始都指向位置0
        * 乘2
        * 乘3
        * 乘5 
    * 每次比較取最小的加入nums，並將該pointer+1
        * 要分別判斷當前最小等於乘2、乘3、乘5
        * 不能用if elif、else...
        * 因為可能碰到公倍數
            * ex: 6，則pointer2、pointer3皆須+1


## Python:
``` python=
class Solution(object):
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        #用3個pointer維護*2*3*5 取最小的加入list 並將該pointer+1
        nums=[1]
        #初始都指向位置0
        p2=0 
        p3=0
        p5=0
        for val in range(n-1):
            tmp=min(nums[p2]*2,nums[p3]*3,nums[p5]*5)
            nums.append(tmp)
            #要分別判斷 不能if elif else...連續
            #因為可能碰到公倍數
            if tmp==nums[p2]*2:
                p2+=1
            if tmp==nums[p3]*3:
                p3+=1
            if tmp==nums[p5]*5:
                p5+=1
        return nums[-1]

result=Solution()
ans=result.nthUglyNumber(n=10)
print(ans)
```

## C++:
``` cpp=
class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int> res(1,1);
        int p2=0, p3=0, p5=0;
        int val=0;
        for (int i=0; i<n-1; i++){
            val=min(min(res[p2]*2, res[p3]*3), res[p5]*5);
            res.push_back(val);
            if (val==res[p2]*2)
                p2+=1;
            if (val==res[p3]*3)
                p3+=1;
            if (val==res[p5]*5)
                p5+=1;
        }
        return res.back();
    }
};
```