Simple, short C++ with one deque


  • 0
    O

    Originally wrote with one list, changed to deque (thanks cbrghostrider) for better memory. Variable i_5 is always 0, included for symmetry

    class Solution {
    public:
        int nthUglyNumber(int n) {
            deque<int> L = {1};
            int i_2=0, i_3=0, i_5=0;
            while(--n){
                int t2 = L[i_2]*2, t3 = L[i_3]*3, t5 = L[i_5]*5;
                int smallest = min(t2, min(t3, t5));
                L.push_back(smallest);
                if (t2==smallest) i_2++;
                if (t3==smallest) i_3++;
                if (t5==smallest) {
                    L.pop_front();
                    i_2--;
                    i_3--;
                }
            }
            return L.back();
        }
    };

  • 0
    O

    Just noticed that this runs over twice as fast if deque is replaced by one list (and code simpler with list - t5==smallest line like others). Still prefer this because better for very large n.


Log in to reply
 

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