313. Super Ugly Number

Write a program to find the nthsuper ugly number.

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

Note:
(1)1is a super ugly number for any givenprimes.
(2) The given numbers inprimesare in ascending order.
(3) 0 <k≤ 100, 0 <n≤ 106, 0 <primes[i]< 1000.
(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.

S：merge sort O(NK)

新的ugly number都由primes乘以已有的ugly number构成，用merge sort顺序生成ugly number，每次将primes.size()个虚拟list中最小的数存储ugly number, 每个list首元素为ugly[index[j]] * primes[j]，当队首元素存入ugly number时index[j]++

    int nthSuperUglyNumber(int n, vector<int>& primes) {
        int size = primes.size();
        vector<int> ugly(n, INT_MAX), index(size, 0);
        ugly[0] = 1;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < size; ++j) {
                ugly[i] = min(ugly[i], ugly[index[j]] * primes[j]);
            }
            for (int j = 0; j < size; ++j) {  //merge进的表头进一位, 包括所有重复元素
                if (ugly[i] == ugly[index[j]] * primes[j]) {
                    index[j]++;
                }
            }
        }
        return ugly[n - 1];
    }

merge sort可由heap 优化为nlogk