public int nthUglyNumber(int n) {
if(n<=0) return 0;
PriorityQueue<Long> queue = new PriorityQueue<>();
Set<Long> set = new HashSet<>();
queue.offer((long)1);
long num=0;
while(n>0 && !queue.isEmpty()){
num = queue.poll();
if(set.contains(num)) continue; //remove duplicate
set.add(num);
queue.offer(num*2);
queue.offer(num*3);
queue.offer(num*5);
n;
}
return (int)num;
}
AC PriorityQueue Solution


@ddoshi5
The space complexity of the DP solution is O(n).For this solution, to generate nth number, there will be n numbers in the set, which means the time complexity is also O(n), plus the space for ProrityQueue, which will also be O(n). Therefore, this solution actually uses more space than DP solution.......