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.
1is a super ugly number for any given primes.- The given numbers in primes are 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.
For example:
[1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first12super ugly numbers given primes =[2, 7, 13, 19]of size4.
C Solution:
Heap:
void dive(int *heap, int *ind, int *primes, int size) {
int root = 1, child = 2;
while (child < size) {
if (child + 1 < size && heap[child] > heap[child + 1]) child++;
if (heap[root] <= heap[child]) return;
int tmp = heap[root];
heap[root] = heap[child];
heap[child] = tmp;
tmp = ind[root];
ind[root] = ind[child];
ind[child] = tmp;
tmp = primes[root - 1];
primes[root - 1] = primes[child - 1];
primes[child - 1] = tmp;
root = child;
child = root * 2;
}
}
int nthSuperUglyNumber(int n, int* primes, int primesSize) {
int *heap = malloc((primesSize + 1) * sizeof(int));
memcpy(heap + 1, primes, primesSize * sizeof(int));
int *ind = calloc(primesSize + 1, sizeof(int));
int *dp = malloc(n * sizeof(int));
dp[0] = 1;
int i, last = 1;
for (i = 1; i < n; i++) {
while (heap[1] <= last) {
do {
heap[1] = dp[++ind[1]] * primes[0];
} while (heap[1] <= last);
dive(heap, ind, primes, primesSize + 1);
}
last = dp[i] = heap[1];
heap[1] = dp[++ind[1]] * primes[0];
dive(heap, ind, primes, primesSize + 1);
}
return dp[n - 1];
}
int nthSuperUglyNumber(int n, int* primes, int primesSize) {
if (n < 2) return n;
int *res = malloc(n * sizeof(int));
int *t = calloc(primesSize, sizeof(int));
int *flag = malloc(primesSize * sizeof(int));
memcpy(flag, primes, primesSize * sizeof(int));
res[0] = 1;
int i, last = 1;
for (i = 1; i < n; i++) {
int j, min = INT_MAX;
for (j = 0; j < primesSize; j++) {
if (flag[j] <= last) {
int prm = primes[j];
flag[j] = prm * res[++t[j]];
}
min = min < flag[j] ? min : flag[j];
}
res[i] = last = min;
}
return res[n - 1];
}
Summary:
- Heap: 19ms, 100%. Loop: 12ms, 100%
- I used heap, which is nice. I also used last, whose target is to remove duplicates. O(lg(primesSize) * n)
- The second solution is O(primesSize * N) time complexity, but it's faster than heap. Sometimes it just happens.
LeetCode: 313. Super Ugly Number
近期评论