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();
    }
};