Super Ugly Number -- leetcode

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.

Note:

(1) 

1

 is a super ugly number for any given 

primes

.

(2) The given numbers in 

primes

 are in ascending order.

(3) 0 < 

k

 ≤ 100, 0 < 

n

 ≤ 106, 0 < 

primes[i]

 < 1000.

题目从一个素数的集合中，任选几个数，进行剩积，得到一系列数。计算出第n个数。

同一个数可被重复选取。

思路：

逐个计算。

第一个数为1.

后续数的计算方法为：在已经得到的数中，分别乘上集合中的每一个数，在新计算出的数中选择最小的值。即为下一个值。

为了避免计算无效的数据，引入k个指针，k为素数集合的个数。指针指向的ugly数与对应的素数之乘积，作为下一个ugly数的备选数。

在上面k个备选数中，选择最小值。 

一旦贡献了最小值，则对应的指针需要指向下一个ugly。

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> index(primes.size());
        vector<int> ugly(n, 1);
        for (size_t i = 1; i < n; ++i) {
            ugly[i] = INT_MAX;
            for (size_t j = 0; j < primes.size(); ++j)
                ugly[i] = min(ugly[i], primes[j] * ugly[index[j]]);
                
            for (size_t j = 0; j < index.size(); ++j)
                if (ugly[i] == primes[j] * ugly[index[j]])
                    ++index[j];
        }
        
        return ugly.back();
    }
};           

上面算法中，第一内循环，是在寻找下一个ugly。

第二个内循环，则是确定，是谁贡献了此次ugly。从而需要将对应的指针向下移。

为了避免重复的乘法操作，将乘法的结果缓存起来。算法改进为：

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> index(primes.size());
        vector<int> ugly(n, 1);
        vector<int> value(primes.size(), 1);
        int next = 1;
        for (size_t i = 0; i < n; ++i) {
            ugly[i] = next;
            next = INT_MAX;
            for (size_t j = 0; j < primes.size(); ++j) {
                if (value[j] == ugly[i])
                    value[j] = ugly[index[j]++] * primes[j];
                    
                next = min(next, value[j]);
            }
        }
        
        return ugly.back();
    }
};