313. Super Ugly Number

Given an integer n and an array of integers primes, return the nth super ugly number.

Super ugly number is a positive number whose all prime factors are in the array primes.

The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

 

Example 1:

Input: n = 12, primes = [2,7,13,19]
Output: 32
Explanation: [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].
Example 2:

Input: n = 1, primes = [2,3,5]
Output: 1
Explanation: 1 is a super ugly number for any given primes.
 

Constraints:

1 <= n <= 106
1 <= primes.length <= 100
2 <= primes[i] <= 1000
primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.

这题和Ugly Number II是一样的，我们既然会了动态规划的方法去求解，那么我们这题也使用该方法。

首先，我们建立一个指针数组，分别指向dp结果集头部，头部值为1。

接着，我们用primes数组里的值去分别和对应的指针数组指向的值相乘，这样我们就能得到一个最小的乘积。我们把这个乘积放入dp数组。同时我们需要去遍历之前乘积的结果，当乘积和其相等，我们需要把指针往前加一，因为该结果我们已经使用过了。

class SuperUglyNumber : public Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> ptrs(primes.size(), 0), dp(n, 1), products(primes.size(), 0);
        int num = 1;
        while (num < n) {
            int minProduct = INT_MAX;
            for (int i = 0; i < primes.size(); i++) {
                products[i] = dp[ptrs[i]] * primes[i];
                if (products[i] < minProduct) minProduct = products[i];
            }
            dp[num++] = minProduct;
            for (int i = 0; i < products.size(); i++) {
                if (products[i] == minProduct) {
                    ptrs[i]++;
                }
            }
        }
        return dp[n - 1];
    }
};