leetcode Super Ugly Number

leetcode Super Ugly Number

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.

super ugly number定义为：整数，且因子全部都在primes中。 注意1为特殊的super ugly number。

C++

Java

Python

3 thoughts on “leetcode Super Ugly Number”

1. YZ says:

你好， 请问c++版本的第26行是不是不用检查q.empty()?

2. Dimitar says:

请问这个算的的时间复杂度是多少呢？我感觉是O(NlogK)但是这个执行时间比O(nk)长很多。
int nthSuperUglyNumber(int n, vector& primes) {
const size_t k = primes.size();
vector uglyNum(n, INT_MAX);
uglyNum[0] = 1;
vector next(k, 0), next_i(k, 0);
for(int i = 0; i < k; ++i)
next[i] = primes[i];
for(int i = 1; i < n; ++i){
for(int j = 0; j < k; ++j)
uglyNum[i] = min(uglyNum[i], next[j]);
for(int j = 0; j < k; ++j)
if(uglyNum[i] == next[j])
next[j] = primes[j] * uglyNum[++next_i[j]];
}
return uglyNum[n – 1];
}

• 对的，我用的优先队列，是O(NlogK)，但是比直接的O(nk)慢，我感觉是因为是使用了自定义的类Node, 比简单的方法要慢，而数据量小，复杂度优势体现不出来。T^T