Share my clear Java accepted solution using 3 queues with explanation


  • 0
    N
    public class Solution {
        public int nthUglyNumber(int n) {
            if(n < 1) return 0;
            
            // initialization: set the 1st ugly number as 1.
            int ugly = 1, count = 1;
            
            // set up 3 queues to store later ugly numbers
            // because the product of two ugly numbers is still an ugly number
            Queue<Integer> q2 = new LinkedList<Integer>();
            Queue<Integer> q3 = new LinkedList<Integer>();
            Queue<Integer> q5 = new LinkedList<Integer>();
            
            // offer them with actually 1*2, 1*3 and 1*5
            // since 1 is the 1st ugly number
            q2.offer(2);
            q3.offer(3);
            q5.offer(5);
            
            while(count != n){
                
                // pick the smallest one among head of each queue
                int min = Math.min(q2.peek(), Math.min(q3.peek(), q5.peek()));
                if(q2.peek() == min) q2.poll();
                else if(q3.peek() == min) q3.poll();
                else q5.poll();
                
                // duplicates may happen
                // then we don't update
                if(ugly != min){
                    ugly = min;
                    count++;
                    q2.offer(ugly * 2);
                    q3.offer(ugly * 3);
                    q5.offer(ugly * 5);
                }
            }
            return ugly;
        } 
    }

Log in to reply
 

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