1、前言

2、思路

本题如果一个个判断的话，会超时。所以应该想的是，基本的底是2、3、5，那么我们可以从 1 开始，不断从小根堆中取出堆顶元素，然后乘2、3、5放入堆中。为了防止放了重复的数，可以使用 set 记录一下是否已经放过。

还要注意一点，为了防止溢出，需要 long 而不是 int。

3、代码

class Solution {
    public int nthUglyNumber(int n) {
        int[] arr = new int[]{2, 3, 5};

        Set<Long> set = new HashSet<>();
        Queue<Long> priorityQueue = new PriorityQueue<>();
        set.add(1l);
        priorityQueue.add(1l);

        for(int i = 1; i <= n; i++){
            long num = priorityQueue.poll();
            if(i == n){
                return (int)num;
            }

            for(int a : arr){
                long t = num * a;
                if(!set.contains(t)){
                    set.add(t);
                    priorityQueue.add(t);
                }
            }
        }

        return -1;
    }
}