給你一個整數 n ，請你找出并返回第 n 個 丑數 。

丑數 就是只包含質因數 2、3 和/或 5 的正整數。

示例 1：

輸入：n = 10
輸出：12
解釋：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 個丑數組成的序列。

解題思路

維護一個最小堆和一個set，記錄以及進入堆的丑數，每次將堆的最小值出隊，并且將它的2，3，5倍數入隊

代碼

class Solution {public int nthUglyNumber(int n) {PriorityQueue<Long> priorityQueue=new PriorityQueue<>();Set<Long> set=new HashSet<>();priorityQueue.add(1L);int cnt=0;while (true){long cur=priorityQueue.poll();cnt++;if(cnt==n)return (int)cur;if(!set.contains(cur*2)){priorityQueue.add(cur*2); set.add(cur*2);}if(!set.contains(cur*3)){priorityQueue.add(cur*3);set.add(cur*3);}if(!set.contains(cur*5)){priorityQueue.add(cur*5);set.add(cur*5);}}}
}