public int nthUglyNumber(int n) {
if(n==1) return 1;
PriorityQueue<Long> q = new PriorityQueue();
q.add(1l);
for(long i=1; i<n; i++) {
long tmp = q.poll();
while(!q.isEmpty() && q.peek()==tmp) tmp = q.poll();
q.add(tmp*2);
q.add(tmp*3);
q.add(tmp*5);
}
return q.poll().intValue();
}
Java solution  using PriorityQueue

The key here is that autoboxing wraps to the corresponding wrapper class:
int
>Integer
andlong
>Long
. While calling a method with along
parameter works, if you pass anint
, because a widening conversion happens. However, Java doesn't try to figure out all the possible widened types and their wrappers, you have to be explicit. Easy to remember:1L == (long)1
. Be careful because(long)2147483648
(and anything above that) is a compile error, while2147483648L
is valid.
There are two other similar suffixes:d
andf
fordouble
andfloat
respectively. The suffixes are case insensitive, but I suggest you prefer10L
,10d
because otherwise it's harder to read due to similarity:10l
vs101
and10
VS1D
.

The elements of the priority queue are ordered according to their natural ordering1, which means all generated numbers are sorted in a priority queue.
So the while loop, is just retrieving every different number.

The elements of the priority queue are ordered according to their natural ordering.
Which means the while loop just retrieving every different numbers from the priority queue.


public class Solution {
public int nthUglyNumber(int n) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
queue.offer(1);
int count = 1;
while(count < n){
int num = queue.poll();
while(!queue.isEmpty() && num == queue.peek()) queue.poll();
count++;
if(num * 2 > 0)
queue.offer(num * 2);
if(num * 3 > 0)
queue.offer(num * 3);
if(num * 5 > 0)
queue.offer(num * 5);
}
return queue.poll();
}
}
Can anyone tell me why this method is wrong??

@www2277843987 Please note that, with this method, we got every uglyNumbers firstly and then we get the least number each time, which means ugly numbers in our priorityqueue are pretty big and out of the range of Integer, so "peng4" use Long instead of Integer and that's your difference with his solution...Please be more careful!

@mariaandjenn Firstly, we store the first ugly number '1' in our priorityQueue, then we remove it from the first element '1' from the queue, and put 12=2,13=3,15=5 into the queue, now our queue store three numbers:2,3,5; Pay attention to '1' we got!
Secondly, we pop out '2' from our queue, and then put 22=4, 23=6, 25=10 into the queue, now there are 3,4,5,6,10 in our queue; Pay attention to '2' we got!
Thirdly,we pop '3' out, and put 32=6, 33=9, 35=15 into our queue, now we have 4,5,6,6,9,15; we remove '3' in this step!
Fourthly,'4' out, 42=8,43=12,45=20 in, and finally 5,6,6,8,9,12,15,20 in the queue.
Fifthly,'5' out, 52=10,53=15,5*5=20 in , and we have 6,6,8,9,10,12,15,15,20,20 in the queue
Sixthly,'6','6' out(Implied by this line " while(!q.isEmpty() && q.peek()==tmp) tmp = q.poll(); ), and ...
...
In this way, we have the chance to meet every ugly numbers in our queue and we will not miss any ugly number; With the help of PriorityQueue, each time we can get the smallest ugly number from the head of our priorityqueue,(one special case is that several numbers in the fornt is the same,such as the queue '6,6,8,9,...' we got in step5, so we pop all '6' out).With i in the range of 1~n1 we remove the first n1 ugly number out of the queue, and finally we call 'q.poll()' one more time, to get the nth ugly number.

@zhwjchww The numbers in PirorQueue are not ordered! PirorQueue can only guarantee the least number at first position. So, i think your example should be more clear. :)

I think to use TreeSet other than PriorityQueue is easier as you don't need to worry about duplicates. Time complexity is same.
public class Solution { public int nthUglyNumber(int n) { TreeSet<Long> ans = new TreeSet<>(); ans.add(1L); for (int i = 0; i < n  1; ++i) { long first = ans.pollFirst(); ans.add(first * 2); ans.add(first * 3); ans.add(first * 5); } return ans.first().intValue(); } }

@yl I think your solution could be improved further. If the total number of added elements reaches n, we could stop adding new candidates to the TreeMap. Then we just need to poll those elements out.