3ms JAVA solution beats 100%


  • 3
    Z

    after some tests the input num n is less than 3000 so............................

    public class Solution {
            static int[] save = new int[3000];
            static int flag = 0;
            public int nthUglyNumber(int n) {
               if(flag == 0){
                   flag ++;
                   init();
               }
               return save[n-1];
            }
            public static void init(){
                int _2 = 0, _3 = 0, _5 = 0;
                save[0] = 1;
                for(int i = 1; i < 3000; i++){
                    int min = Math.min(save[_2]*2, Math.min(save[_3]*3,save[_5]*5));
                    if(save[_2]*2 == min) {
                        save[i] = save[_2]*2;
                        _2 ++;
                    }
                    if(save[_3]*3 == min) {
                        save[i] = save[_3]*3;
                        _3 ++;
                    }
                    if(save[_5]*5 == min) {
                        save[i] = save[_5]*5;
                        _5 ++;
                    }
                }
            }
        }

  • 0
    P

    Finally, someone else using doing table lookup!

    Could limit array size to 1692 and avoid storing values involving overflow.

    Could also use static initializer block (demonstrating greater mastery of Java) instead of flag & init() to initialize the lookup table. Your approach does have the advantage of not wasting time filling the table if the class is loaded and an instance is created, but for some reason the function is not called.

    Could be made more elegant by only building the part of the table actually needed by using more static variables instead of function local variables.


  • 0
    C

    you can just replace 3000 with n


Log in to reply
 

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