---
# System prepended metadata

title: Leetcode 264. Ugly Number II
tags: [Leetcode(C++)]

---

# Leetcode 264. Ugly Number II
###### tags: `Leetcode(C++)`

題目 : https://leetcode.com/problems/ugly-number-ii/submissions/ 。

想法 : 

    用priority_queue找順序，用set紀錄是否已經出現過避免重複儲存。

時間複雜度 : O(nlogn)。

程式碼 :

```
typedef long long int LL;

class Solution {
public:
    int nthUglyNumber(LL n) {
        priority_queue<LL, vector<LL>, greater<LL> > pq;
        set<LL> s;
        int cnt=1;
        
        pq.push(1); s.insert(1);
        while(cnt < n){
            LL tmp=pq.top(); pq.pop(); cnt++;
            if(s.count(tmp*2) == 0){
                pq.push(tmp*2);
                s.insert(tmp*2);
            }
            if(s.count(tmp*3) == 0){
                pq.push(tmp*3);
                s.insert(tmp*3);
            }
            if(s.count(tmp*5) == 0){
                pq.push(tmp*5);
                s.insert(tmp*5);
            }
        }
        
        return pq.top();
    }
};
```