C++ solution with O(n) time


  • 11
    F

    class Solution {
    public:
    int nthUglyNumber(int n) {
    int i=0;
    int j=0;
    int k=0;
    vector<int> v;
    v.push_back(1);

            while(v.size()!=n){
                   int m=min(v[i]*2,min(v[j]*3,v[k]*5));
    	   if(m==v[i]*2) i++;
    	   if(m==v[j]*3) j++;
    	   if(m==v[k]*5) k++;
                   v.push_back(m);  
            }
            return v.back();
        }
    

    };


  • 0
    K

    nice solution!


  • 0
    L

    I do not understand why it could not come out this situation that given x, y, z, x2 for example is the smallest, but x2 was already in the vector?
    Could you please explain this for me?


Log in to reply
 

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