O( n) JAVA---Easy version to understand!


  • 7
    H
        int getMin(int a,int b,int c){
         int min=Integer.min(a,b);
         min=Integer.min(min,c);
         return min;
    }
    public int nthUglyNumber(int n) {
        if(n==1)
          return 1;
          int[] a=new int[n];
        int p2=0,p3=0,p5=0,p=1,count=1;
         a[0]=1;
        while(count<n){
            a[p]=getMin(a[p2]*2,a[p3]*3,a[p5]*5);
            while(a[p2]*2<=a[p])
               p2++;
            while(a[p3]*3<=a[p])
               p3++;
            while(a[p5]*5<=a[p])
               p5++;
              
              p++;
              count++;
        }
        return a[--p];
    }

Log in to reply
 

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