AC PriorityQueue Solution


  • 2
    R
    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;
        }
    

  • 0
    D

    I think this is a great solution and can save a lot of space when the N is very very large. All the other dynamic programming solutions wont be as effective when N is very large as space will be a constrain.


  • 0
    F

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


Log in to reply
 

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