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.
Example:
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 givenprimes=[2,7,13,19]of size 4.
Note:
1is a super ugly number for any givenprimes.- The given numbers in
primesare in ascending order. - 0 <
k≤ 100, 0 <n≤ 106, 0 <primes[i]< 1000. - The nth super ugly number is guaranteed to fit in a 32-bit signed integer.
Solution 1: Set
Maintain an ordered set of super ugly numbers, each time extract the smallest one, and multiply it with all primes and insert the new number into set.
Time complexity: O(n*k*logn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua, running time: 484 ms class Solution { public: int nthSuperUglyNumber(int n, vector<int>& primes) { if (n == 1) return 1; set<int> q{begin(primes), end(primes)}; for (int i = 0; i < n - 2; ++i) { auto it = begin(q); int t = *it; q.erase(it); for (int p : primes) { if (INT_MAX / t < p) continue; q.insert(p * t); } } return *begin(q); } }; |
Solution 2: Priority Queue
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
// Author: Huahua, 40 ms struct Node { int num; int index; int prime; bool operator>(const Node& o) const { if (this->num == o.num) return this->index > o.index; return this->num > o.num; } }; class Solution { public: int nthSuperUglyNumber(int n, vector<int>& primes) { if (n == 1) return 1; vector<int> nums(n, 1); priority_queue<Node, vector<Node>, greater<Node>> q; for (int p : primes) q.push({p, 1, p}); for (int i = 1; i < n; ++i) { nums[i] = q.top().num; while (nums[i] == q.top().num) { Node node = std::move(q.top()); q.pop(); node.num = nums[node.index++] * node.prime; q.push(std::move(node)); } } return nums.back(); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment