Java solution -- using PriorityQueue


  • 25
    P
    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();
    }

  • 1
    C

    I'm confused with " q.add(1l);"
    what does 1l means? anyone can help? thanks.


  • 2
    L

    He is specifying that he's adding a "long" 1 to the queue rather than int 1. His queue is of type Long, so you can only add longs, not ints.

    A "long" has 64 bits, so it can store much larger numbers than the 32 bit "int".


  • 2
    J

    Nice solution. You can probably just q.poll() instead of tmp=q.poll();


  • 1
    T

    The key here is that auto-boxing wraps to the corresponding wrapper class: int -> Integer and long -> Long. While calling a method with a long parameter works, if you pass an int, 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, while 2147483648L is valid.
    There are two other similar suffixes: d and f for double and float respectively. The suffixes are case insensitive, but I suggest you prefer 10L, 10d because otherwise it's harder to read due to similarity: 10l vs 101 and 10 VS 1D.


  • 0
    M

    Can you briefly explain the basic logic of this priority queue implementation? Especially the while loop. Thank you


  • 0

    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.


  • 0

    @mariaandjenny

    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.


  • 0
    D

    Good Solution.


  • 0
    X

    @Check4Tblue l means long


  • 0
    W

    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??


  • 0
    Z

    @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!


  • -1
    Z

    @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 2
    2=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, 4
    2=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~n-1 we remove the first n-1 ugly number out of the queue, and finally we call 'q.poll()' one more time, to get the nth ugly number.


  • 0
    S

    @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. :)


  • 5
    Y

    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();
        }
    }
    

  • 0
    P

    Should we keeps adding 3 new elements to the PriorityQueue each round? Once the added elements reaches n, we could stop adding. But we should worry about the duplicates, hence TreeMap probably a better alternative to PriorityQueue.


  • 1
    P

    @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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.