Java solution using PriorityQueue. O(nlg(n))


  • 1
    Q

    This is really O(n) performance as Binary Heap is O(1) insert performance on average.

    public int nthUglyNumber(int n) {
        int index=0;
        PriorityQueue<Long> q = new PriorityQueue<Long>();
        q.offer(1L);
        int i=0;
        long prev=0;
        while(i++<n){
            long val = q.poll();
            while (val == prev){
                val = q.poll();
            }
            prev = val;
            for (long ugly: new long[]{val*2, val*3, val*5}){
                q.offer(ugly);
            }
        }
        return (int)prev;
    }

  • 1
    L

    simplify the code

    public int nthUglyNumber(int n) {
        PriorityQueue<Long> q = new PriorityQueue<Long>();
    	q.offer(1l);
    	long cur = 0;
    	while(n-->0){
    		while(q.peek()==cur){
    			q.poll();
    		}
    		cur = q.poll();
    		q.offer(cur*2);
    		q.offer(cur*3);
    		q.offer(cur*5);
    	}
    	return (int)cur;
    }
    

  • 0
    Q

    Thanks, I'm glad someone took effort to understand my ugly code :)


  • 0

    This is really O(n) performance as Binary Heap is O(1) insert performance on average

    I doubt it. Do you have a reference for that?

    Also, if that were true, and poll also averaged O(1) as your "O(n) total" claim suggests, then you'd have a method for sorting in O(n), no?


  • 0
    Q

    https://www.youtube.com/watch?v=B7hVxCmfPtM start with min 39.
    You're right about the poll though it's log(n) not O(1). So total is O(nlg(n))


  • 0

    I haven't watched it all, but I think he's talking about the "smart" way to heapify, not about using insertions. Quote from Wikipedia:

    A heap could be built by successive insertions. This approach requires O(n log n) time because each insertion takes O(log n) time and there are n elements. However this is not the optimal method. The optimal method ...

    And I think what follows there is what the guy in your video is doing. Not doing insertions.

    What do you think?


  • 0
    Q

    Guy in video is doing insertions. From the same wikipedia article

    Insert[edit]
    To add an element to a heap we must perform an up-heap operation (also known as bubble-up, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up), by following this algorithm:

    Add the element to the bottom level of the heap.
    Compare the added element with its parent; if they are in the correct order, stop.
    If not, swap the element with its parent and return to the previous step.
    The number of operations required is dependent on the number of levels the new element must rise to satisfy the heap property, thus the insertion operation has a time complexity of O(log n). However, in 1974, Thomas Porter and Istvan Simon proved that the function for the average number of levels an inserted node moves up is upper bounded by the constant 1.6067.[1] The average number of operations required for an insertion into a binary heap is 2.6067

    Also we are increasing numbers as we progress which should make C constant even less.


  • 0
    S

    It should be O(nlongn) because the operation of adjustment of heap should be logN, so total is nlogn.


  • 0
    Q

    I will correct the heading as poll() is lg(n) due to heap rebuilding as mentioned above.


Log in to reply
 

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