我們把只包含質因子 2、3 和 5 的數稱作丑數（Ugly Number）。求按從小到大的順序的第 n 個丑數。

示例:

輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數。
說明:

• 1 是丑數。
• n 不超過1690。

解題思路

1. 使用小根堆，每次從小根堆拿出一個元素cur，并且將cur *2，cur *3,cur *5加入小根堆，當第n次從小根堆出隊的元素就是第n個丑數

代碼

class Solution {public int nthUglyNumber(int n) {PriorityQueue<Long> priorityQueue=new PriorityQueue<>();HashSet<Long> hashSet=new HashSet<>();priorityQueue.add(1L);hashSet.add(1L);for (int i=0;i<n-1;i++){long cur = priorityQueue.poll();if (!hashSet.contains(cur*2)){hashSet.add(cur*2);priorityQueue.add(cur*2);}if (!hashSet.contains(cur*3)){hashSet.add(cur*3);priorityQueue.add(cur*3);}if (!hashSet.contains(cur*5)){hashSet.add(cur*5);priorityQueue.add(cur*5);}}return (int)priorityQueue.poll().longValue();}
}