Super Ugly Number

1. 解析

这道题Ugly Number II 的升级版，题目大意，求解第n个super Ugly Number，super Ugly Number(除1之外)的因子只存在因子列表primes中，换汤不换药，只是将3个因子改成了n个因子

2. 分析

最直接的做法就是利用优先队列，每次取出最小的数，然后依次和因子列表primes中的每个因子依次相乘，以产生下一个super Ugly Number，为了过滤掉已经出现过的数，将已经产生的数在hashtable中备份，每次先在hashtable中先检索产生的ugly Number是否出现过，若没有，放进队列，若已经存在，不放进队列里面。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long long, vector<long long>, greater<long long>> nums(1, 1);
        map<long long, bool> exist;
        
        while (--n > 0){
            long long num = nums.top();
            nums.pop();
            for (auto prime: primes){
                if (exist[prime*num]) continue; //若产生的数之前已经产生过，不放进队列
                nums.push(prime*num);
                exist[prime*num] = true;
            }
            
        }
        return nums.top();
    }
};

3. 动态规划法

由3个变量替换成n个元素的数组即可，详见 Ugly Number II

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes){
        vector<int> counts(primes.size(), 0);
        vector<int> nums(primes.size());
        vector<int> res(1, 1);
        while (res.size() < n){
            int minNum = INT_MAX;
            for (int i = 0; i < primes.size(); ++i){
                nums[i] = primes[i] * res[counts[i]];
                if (minNum > nums[i])
                    minNum = nums[i];
            } 
            res.push_back(minNum);
            for (int i = 0; i < nums.size(); ++i) if (minNum == nums[i]) counts[i]++;
        }
        return res.back();
    }
};

4. 类似题目 

 Ugly Number II