Share my 4ms cpp solution beats 98.9% submissions


  • 11
    S
    class Solution {
    public:
        int nthUglyNumber(int n) {
            static vector<int> ugly{0, 1};
            static int m1 = 1, m2 = 1, m3 = 1;
            if (n < ugly.size()) {
                return ugly[n]; 
            }
            int next = 0;
            while(n >= ugly.size()) {
                next = min(ugly[m1] * 2, min(ugly[m2] * 3, ugly[m3] * 5));
                ugly.push_back(next);
                if (ugly[m1] * 2 == next) {
                    ++m1;
                }
                if (ugly[m2] * 3 == next) {
                    ++m2;
                }
                if (ugly[m3] * 5 == next) {
                    ++m3;
                }
            }
            return ugly[n];
        }
    };

  • 10
    W

    I find a interesting thing.
    If I remove the "static" from your code, the speed will be decreased a lot.
    so I think all tests are just running in one main function in leetcode. That means you can use static or global to remember some dp status to speed up your codes.


Log in to reply
 

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