Why O(NlogK) algorithm takes longer running time than O(NK) algorithm


  • 1
    R

    This solution avoid repeated multiplication, but the running time is 384ms, larger then the O(NK) algorithm

       class Solution {
        public:
            int nthSuperUglyNumber(int n, vector<int>& primes) {
                if (n <= 1) return 1;
                vector<int> index(primes.size());
                vector<int> uglyNumbers(n);
                uglyNumbers[0] = 1;
                using val_pair = pair<int, size_t>;
                priority_queue<val_pair, vector<val_pair>, greater<val_pair>> pq;
                for (int j = 0; j < primes.size(); ++j) {
                    if (uglyNumbers[index[j]])
                        pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
                }
                for (int i = 1; i < n; ++i) {
                    if (!pq.empty()) {
                        auto top = pq.top();
                        pq.pop();
                        uglyNumbers[i] = top.first;
                        int j = top.second;
                        index[j]++;
                        pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
                        while (!pq.empty() && pq.top().first == top.first) {
                            auto next = pq.top();
                            pq.pop();
                            j = next.second;
                            index[j]++;
                            pq.push(make_pair(primes[j]*uglyNumbers[index[j]], j));
                        }                
                    }
        
                }
                return uglyNumbers.back();
            }
        };

  • 0

    Same here for Java Solution, I think this is because it has the overhead of maintaining priority queue and constructing & destructing pairs, and also it has to deal with duplicates. All this will not have much performance gain for relatively small value of k


Log in to reply
 

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