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.

分析：

这道题目本身跟Ugly Number II的思路是完全相同的，只是过程略微复杂。

解法：

class Solution {
public:
    /**
     * @param n a positive integer
     * @param primes the given prime list
     * @return the nth super ugly number
     */
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        // Write your code here
        if (n <= 0) {
            return 0;
        }
        vector<int> res;
        res.push_back(1);

        vector<int> coeffi(primes.size(), 0);
        for (int i = 1; i < n; i++) {
            // find min
            int newUgly = INT_MAX;
            for (int j = 0; j < primes.size(); j++) {
                newUgly = min(newUgly, primes[j] * res[coeffi[j] ]);
            }
            for (int j = 0; j < primes.size(); j++) {
                if (newUgly == primes[j] * res[coeffi[j] ]) {
                    coeffi[j] += 1;
                }
            }
            res.push_back(newUgly);
        }
        return res[n - 1];
    }
};