题目描述

给定primes数组。
定义第一个超级丑陋数一定为1.
求解超级丑陋数。
超级丑陋数定义如下：
超级丑陋数是正数，并且质因子在给定的primes列表中。并且超级丑陋数是从小到大排列的。
数的限制导致一般的乘积不会爆int。

样例如下

样例

给定k = 4 个素数。
primes = [2, 7, 13, 19]
超级丑陋数顺序如下所示
[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]
第5个超级丑陋数为8

算法

(模拟) $O(n*k)$

分析：
1 观察后我们发现，我们一定需要知道所有超级丑陋数，假设求第n个，那么一定需要知道前n-1个。
这有点像求素数，我们想知道第n个素数，一定得知道前n-1个。

2 超级丑陋数一定由多个primes相乘得到，不属于这个primes里面的数，不会作为因子。

3 我们可以认为，任意一个丑陋数，可以写成指数幂的形式，每一个丑陋数都是一步一步得到的。

解答：
由于每一个超级丑陋数都是由当前的某一个因子乘以之前的某一个超级丑陋数得到的。
对于每一个因子，我们只需要记录他走到哪一个超级丑陋数上了（从小往大走）。
因此index[j]就是记录当前第j个primes 对应的那个超级丑陋数的下标。
这样计算有可能会有相同的值，因此我们要和res里面最后一个值做判断，如果相等，那么只移动指针，并不做改变。

时间复杂度分析：一共找n个，每次遍历k次。 所以复杂度为$O(n*k)$

C++ 代码

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int idx = 1;
        vector<int> res;
        vector<int> index;
        index.resize(primes.size());
        res.push_back(1);

        while(idx<n){
            int minval = INT_MAX;
            int minindex = -1;
            for(int i = 0;i<primes.size();++i){
                if (primes[i]*res[index[i]] < minval){
                    minval = res[index[i]] * primes[i];
                    minindex = i;
                }
            }
            index[minindex]++;
            if (minval == res.back()) continue;
            res.push_back(minval);
            idx = idx + 1;
        }
        return res.back();
    }
};