###### 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:

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++:

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();
    }
};