C++ Solution with 3 queue, O(n) time complexity


  • 0
    E
    typedef long long ll;
    
    class Solution {
    public:
        int nthUglyNumber(int n) {
            if(n==1) return 1;
            queue<ll> q2, q3, q5; // remember to use long long
            q2.push(2);
            q3.push(3);
            q5.push(5);
            int count = 1;
            while(true){
                ll n2 = q2.front(), n3 = q3.front(), n5 = q5.front();
                if(n2 < n3 && n2 < n5){  // n2 is the smallest
                    q2.pop();
                    count++;
                    if(count==n) return n2;
                    q2.push(n2*2);
                    q3.push(n2*3);
                    q5.push(n2*5);
                }
                else if(n3 < n2 && n3 < n5){  // n3 is the smallest
                    q3.pop();
                    count++;
                    if(count==n) return n3;
                    q3.push(n3*3);
                    q5.push(n3*5);
                }
                else{
                    q5.pop();
                    count++;
                    if(count==n) return n5;
                    q5.push(n5*5);
                }
            }
            return 1;
        }
    };
    

Log in to reply
 

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