Need Help. The following Java code got TLE


  • 0
    S
    public int nthUglyNumber(int n) {
        LinkedList<Integer> num2 = new LinkedList<Integer>();
        LinkedList<Integer> num3 = new LinkedList<Integer>();
        LinkedList<Integer> num5 = new LinkedList<Integer>();
        int prev = 1;
        num2.add(1);
        num3.add(1);
        num5.add(1);
        int k = 1;
        int min = 1;
        while (k < n) {
            boolean b = false;
            min = num2.peek() * 2;
            if (num3.peek() * 3 < min) {
                min = num3.peek() * 3;
                b = true;
            }
            if (num5.peek() * 5 < min) {
                min = num5.poll() * 5; // here we know the minimum is from num5 list
            } else if (b) {
                num3.poll();
            } else {
                num2.poll();
            } 
            if (prev < min) {
                k ++;
            }
            prev = min;
            num2.add(min);
            num3.add(min);
            num5.add(min);
        }
        return min;
    }
    

    So help me please, which part of the code is too expensive to pass the test? It fails when the input is around 260.


  • 0
    U

    I think to add to the list and to get the value at the end of the list cost too much time. You don't really need to do that. You can use a vector(say vector<int> ugly) to store all the ugly numbers and use three iterators: it2, it3, it5 to do the job of your linked lists. Initially, they all point to the first value in the vector, which is "1". For each loop, you check whether *it2 * 2 > ugly[ugly.size( )-1] (the current largest ugly number). If not, it2++ until the condition is true.
    Do the same thing for all the three iterators, then the next ugly number is just the smallest among *it2 * 2, *it3 * 3, *it5 * 5. The loop ends until ugly.size( ) gets to "n".


  • 0
    U

    I thought you were using c++...anyway, the idea is the same.


Log in to reply
 

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