How to improve my 56ms solution to 36ms?


  • 0
    M
    class Solution {
    public:
        int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> superUgly(n);   // used to store the first n super ugly numbers
        superUgly[0] = 1;
        
        int prime_size = primes.size();
        vector<int> indices(prime_size);    // used to store the indices related to primes
        vector<int> buffer(primes.begin(), primes.end());   // used to store the ugly numbers related to each prime
        vector<int> min_pos_vec(prime_size);    // used to store the indices of the minimum ugly numbers stored in buffer
        
        int INTMAX = numeric_limits<int>::max();
        int ordinal = 0;
        while (++ordinal < n) {
            superUgly[ordinal] = INTMAX;
            int min_pos_index = 0;
            for (int i = 0; i < prime_size; i++) {
                if (buffer[i] > superUgly[ordinal]) continue;
                if (buffer[i] < superUgly[ordinal]) {
                    superUgly[ordinal] = buffer[i];
                    min_pos_index = 0;
                }
                min_pos_vec[min_pos_index++] = i;
            }
            for (int i = 0; i < min_pos_index; i++) {
                int index = min_pos_vec[i];
                indices[index]++;
                buffer[index] = superUgly[indices[index]] * primes[index];
            }
        }
        
        return superUgly[n - 1];
        }
    
    };

Log in to reply
 

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