313. Super Ugly Number

  • 37.2%

https://leetcode.com/problems/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.

(4) The nth super ugly number is guaranteed to fit in a 32-bit signed integer.


方法一:

我的代码实现:

一个primes数组,一个primes对应的indexs数组,一个res数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
int k = primes.size();
vector<int> indexs(k, 0);
vector<int> res(n, INT_MAX);
res[0] = 1;
for(int i=1; i<n; i++){
for(int j=0; j<k; j++)
res[i] = min(res[i], res[indexs[j]]*primes[j]);
for(int j=0; j<k; j++)
if(res[indexs[j]]*primes[j]==res[i])
indexs[j]++;
}
return res[n-1];
}
};

https://leetcode.com/problems/super-ugly-number/

Keep k pointers and update them in each iteration. Time complexity is O(kn).

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
ugly[0]=1;
for(int i=1; i<n; i++){
for(int j=0; j<primes.size(); j++) ugly[i]=min(ugly[i],ugly[index[j]]*primes[j]);
for(int j=0; j<primes.size(); j++) index[j]+=(ugly[i]==ugly[index[j]]*primes[j]);
}
return ugly[n-1];
}
};

方法二:

其实跟方法一是一样的

156ms, 44.15%, May.3rd, 2016

https://leetcode.com/discuss/74625/112ms-c-solution-with-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> superUglyNumbers;
superUglyNumbers.push_back(1);
int numPrimes = primes.size();
vector<int> idxs(numPrimes, 0);

while(superUglyNumbers.size() < n){
int nextSuperUglyNumber = superUglyNumbers[idxs[0]] * primes[0];
for(int i = 0; i < numPrimes; i++)
nextSuperUglyNumber = min(nextSuperUglyNumber, superUglyNumbers[idxs[i]] * primes[i]);
for(int i = 0; i < numPrimes; i++)
if(nextSuperUglyNumber == superUglyNumbers[idxs[i]] * primes[i]) idxs[i]++;
superUglyNumbers.push_back(nextSuperUglyNumber);
}
return superUglyNumbers[n-1];
}
};

164ms, 35.72%, 83 / 83, May.3rd, 2016

https://leetcode.com/discuss/72878/7-line-consice-o-kn-c-solution

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> index(primes.size(), 0), ugly(n, INT_MAX);
ugly[0] = 1;
for(int i = 1; i < n; i++){
for(int j = 0; j < primes.size(); j++) ugly[i] = min(ugly[i], ugly[index[j]] * primes[j]);
for(int j = 0; j < primes.size(); j++) index[j] += (ugly[i] == ugly[index[j]] * primes[j]);
}
return ugly[n-1];
}
};

python

Solution 1:

540ms, 76.45%, 83 / 83, May.3rd, 2016

https://leetcode.com/discuss/72763/python-generators-on-a-heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
uglies = [1]
def gen(prime):
for ugly in uglies:
yield ugly * prime
merged = heapq.merge(*map(gen, primes))
while len(uglies) < n:
ugly = next(merged)
if ugly != uglies[-1]:
uglies.append(ugly)
return uglies[-1]

java

https://discuss.leetcode.com/topic/34841/java-three-methods-23ms-36-ms-58ms-with-heap-performance-explained

Basic idea is same as ugly number II, new ugly number is generated by multiplying a prime with previous generated ugly number. One catch is need to remove duplicate

Let’s start with the common solution from ugly number II 36 ms, Theoretically O(kN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int nthSuperUglyNumberI(int n, int[] primes) {
int[] ugly = new int[n];
int[] idx = new int[primes.length];

ugly[0] = 1;
for (int i = 1; i < n; i++) {
//find next
ugly[i] = Integer.MAX_VALUE;
for (int j = 0; j < primes.length; j++)
ugly[i] = Math.min(ugly[i], primes[j] * ugly[idx[j]]);

//slip duplicate
for (int j = 0; j < primes.length; j++) {
while (primes[j] * ugly[idx[j]] <= ugly[i]) idx[j]++;
}
}

return ugly[n - 1];
}

If you look at the above solution, it has redundant multiplication can be avoided, and also two for loops can be consolidated into one. This trade-off space for speed. 23 ms, Theoretically O(kN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n];
int[] idx = new int[primes.length];
int[] val = new int[primes.length];
Arrays.fill(val, 1);

int next = 1;
for (int i = 0; i < n; i++) {
ugly[i] = next;

next = Integer.MAX_VALUE;
for (int j = 0; j < primes.length; j++) {
//skip duplicate and avoid extra multiplication
if (val[j] == ugly[i]) val[j] = ugly[idx[j]++] * primes[j];
//find next ugly number
next = Math.min(next, val[j]);
}
}

return ugly[n - 1];
}

Can we do better? Theoretically yes, by keep the one candidates for each prime in a heap, it can improve the theoretical bound to O( log(k)N ), but in reality it’s 58 ms. I think it’s the result of using higher level object instead of primitive. Can be improved by writing an index heap (http://algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html)

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
32
33
34
public int nthSuperUglyNumberHeap(int n, int[] primes) {
int[] ugly = new int[n];

PriorityQueue<Num> pq = new PriorityQueue<>();
for (int i = 0; i < primes.length; i++) pq.add(new Num(primes[i], 1, primes[i]));
ugly[0] = 1;

for (int i = 1; i < n; i++) {
ugly[i] = pq.peek().val;
while (pq.peek().val == ugly[i]) {
Num nxt = pq.poll();
pq.add(new Num(nxt.p * ugly[nxt.idx], nxt.idx + 1, nxt.p));
}
}

return ugly[n - 1];
}

private class Num implements Comparable<Num> {
int val;
int idx;
int p;

public Num(int val, int idx, int p) {
this.val = val;
this.idx = idx;
this.p = p;
}

@Override
public int compareTo(Num that) {
return this.val - that.val;
}
}

my code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int numPrimes = primes.length;
int[] idxs = new int[numPrimes];
int[] superUglyNumber = new int[n];
superUglyNumber[0] = 1;

for(int i=1; i<n; i++){
int nextUglyNumber = Integer.MAX_VALUE;
for(int j=0; j<numPrimes; j++)
nextUglyNumber = Math.min(nextUglyNumber, superUglyNumber[idxs[j]]*primes[j]);
for(int k=0; k<numPrimes; k++)
if(nextUglyNumber == superUglyNumber[idxs[k]]*primes[k])
idxs[k]++;
superUglyNumber[i] = nextUglyNumber;
}

return superUglyNumber[n-1];
}
}

谢谢你,可爱的朋友。