[LeetCode] 313. Super Ugly Number

[frdmu]

A super ugly number is a positive integer whose prime factors are in the array primes.

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

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 has no prime factors, therefore all of its prime factors are in the array primes = [2,3,5].

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.

 

解法一：
多指针排序。题解说这是动态规划，是个锤子，其实就是多指针排序，和动态规划有毛关系。每次都取当前能得到的最小丑数。与[LeetCode] 264. Ugly Number II不同就在于得到的数和前一个丑数会有重复，这时只需要移动指针即可。代码如下：

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        vector<int> dp(n+1);
        dp[1] = 1;
        int m = primes.size();
        vector<int> p(m, 1);

        for (int i = 2; i <= n; i++) {
            int Min = INT_MAX, j = 0, index = -1; 
            for (auto prime: primes) {
                int tmp = dp[p[j]] * prime;
                if (tmp < Min) {
                    index = j;
                    Min = tmp;
                }
                j++;
            }
            if (Min > dp[i-1]) {
                dp[i] = Min;
            } else {
                i--;
            }
            p[index]++;
        }

        return dp[n];
    }
};

解法二：
小顶堆。代码如下：

class Solution {
public:
    int nthSuperUglyNumber(int n, vector<int>& primes) {
        priority_queue<long, vector<long>, greater<long>> heap;
        unordered_set<long> hash;

        heap.push(1);
        hash.insert(1);
        int res, cnt = 0; 
        while (!heap.empty()) {
            res = heap.top();
            cnt++;
            if (cnt == n) break;
            heap.pop();
            for (auto prime: primes) {
                long tmp = (long)prime * res;
                if (hash.count(tmp) == 0) {
                    heap.push(tmp);
                    hash.insert(tmp);        
                }
            }
        }

        return res;
    }
};

类似题目：
[LeetCode] 264. Ugly Number II