- Super Ugly Number
Medium
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 1 2 primes[i] is guaranteed to be a prime number.
All the values of primes are unique and sorted in ascending order.
解法1：用Heap做。注意去重可以用topNode.product != uglys[index]。
struct Node {
int prime;
int index;
long long product;
Node(int pri, int id, long long pro) : prime(pri), index(id), product(pro) {}
bool operator (const Node & node) const {
return product >= node.product;
}
};
class Solution {
public:
int nthSuperUglyNumber(int n, vectorint>& primes) {
int primesCount = primes.size();
vectorlong long> uglys(n + 1, 0);
vectorint> indexes(primesCount, 1);
priority_queueNode> minHeap;
uglys[1] = 1;
int index = 1;
for (int i = 0; i primesCount; i++) {
minHeap.push(Node(primes[i], 1, primes[i])服务器托管网); //1 * primes[i] = primes[i]
}
while (index n) {
in服务器托管网t minV = INT_MAX;
Node topNode = minHeap.top();
minHeap.pop();
if (topNode.product != uglys[index]) {
if (index n) {
uglys[++index] = topNode.product;
}
else break;
}
minHeap.push(Node(topNode.prime, topNode.index + 1, uglys[topNode.index + 1] * topNode.prime));
}
return (int)uglys[n];
}
};
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
相关推荐: 2023 年最适用于工业物联网领域的三款开源 MQTT Broker
MQTT 最初作为一种轻量级的发布/订阅消息传递协议而设计，如今已经成为工业物联网（IIoT）和工业 4.0 发展的重要基础。它的意义在于实现了各类工业设备与云端的无缝连接，促进了运营技术（OT）和信息技术（IT）的融合。 本文对比分析了 2023 年工业物联…
