leecode_313 Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32] is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.

(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

c++ multiset 实现：

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        multiset<int> asc_list;
        unordered_map<int,int> map;
        vector<int> res={1};
        vector<int> pointer;
        for (int i=0;i<primes.size();i++)
             pointer.push_back(0);
        for (int i=0;i<primes.size();i++){
            asc_list.insert(res[ pointer[i] ]*primes[i]);
            map[res[ pointer[i] ]*primes[i]]=i;
        }
        
        for (int i=1;i<n;i++){
            int min=*asc_list.begin();
            //cout<<min<<" ";
            res.push_back(min);
            asc_list.erase(asc_list.begin());
            int j=map[min];
            //cout<<" for "<<j<<" ";
            
            pointer[j]++;
            while(map.find(res[ pointer[j] ]*primes[j])!=map.end())
                  pointer[j]++;
                  
            asc_list.insert(res[ pointer[j] ]*primes[j]);
            map[res[ pointer[j] ]*primes[j]]=j;
            //cout<<"add "<<res[ pointer[j] ]*primes[j]<<endl;
            
        }
         
        return res[n-1];    
    }
};

c++ priority_queue 实现

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<int, vector<int>, greater<int>> pqi;
        unordered_map<int,int> map;
        vector<int> res={1};
        vector<int> pointer;
        for (int i=0;i<primes.size();i++)
             pointer.push_back(0);
        for (int i=0;i<primes.size();i++){
            pqi.push(res[ pointer[i] ]*primes[i]);
            map[res[ pointer[i] ]*primes[i]]=i;
        }
        
        for (int i=1;i<n;i++){
            int min=pqi.top();
            pqi.pop();
            //cout<<min<<" ";
            res.push_back(min);
            int j=map[min];
            //cout<<" for "<<j<<" ";
            
            pointer[j]++;
            while(map.find(res[ pointer[j] ]*primes[j])!=map.end())
                  pointer[j]++;
                  
            pqi.push(res[ pointer[j] ]*primes[j]);
            map[res[ pointer[j] ]*primes[j]]=j;
            //cout<<"add "<<res[ pointer[j] ]*primes[j]<<endl;
            
        }
         
        return res[n-1];    
    }
};