# [LeetCode] 313. Super Ugly Number 超级丑陋数

2021年09月15日 阅读数：1

Write a program to find the `nth` super ugly number.html

Super ugly numbers are positive numbers whose all prime factors are in the given prime list `primes` of size `k`.java

Example:python

```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]` of size 4.```

Note:数组

• `1` is 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.

264. Ugly Number II 的拓展，仍是找出第n个丑陋数，但质数集合不在只是2，3，5，而是能够任意给定。难度增长了，但本质上和Ugly Number II 没有什么区别，因为不知道质数的个数，能够用一个idx数组来保存当前的位置，而后从每一个子链中取出一个数，找出其中最小值，而后更新idx数组对应位置，注意有可能最小值不止一个，要更新全部最小值的位置。app

Java:

```public int nthSuperUglyNumber(int n, int[] primes) {
int[] ugly = new int[n+1];
ugly[0]=1;
int[] pointer = new int[primes.length];
for(int i=1;i<n;i++) {
int min=Integer.MAX_VALUE;
int minIndex = 0;
for(int j=0;j<primes.length;j++) {
if(ugly[pointer[j]]*primes[j]<min) {
min=ugly[pointer[j]]*primes[j];
minIndex = j;
}else if(ugly[pointer[j]]*primes[j]==min) {
pointer[j]++;
}
}
ugly[i]=min;
pointer[minIndex]++;
}
return ugly[n-1];
}
```

Java:1

```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];
}
```

Java:2

```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];
}
```

Java: 3 index heap

```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;
}
}　```

Python:

```def nthSuperUglyNumber(self, n, primes):
ugly = [1]
pointers = [0]*len(primes)

for i in range(1,n):
minu = float("inf")
minIndex = 0
for j in range(len(primes)):
if primes[j] * ugly[pointers[j]] < minu:
minu = primes[j] * ugly[pointers[j]]
minIndex = j
elif primes[j] * ugly[pointers[j]] == minu:
pointers[j] += 1
ugly.append(minu)
pointers[minIndex] += 1
return ugly[-1]　　```

Python:

```# Heap solution. (620ms)
class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
heap, uglies, idx, ugly_by_last_prime = [], [0] * n, [0] * len(primes), [0] * n
uglies[0] = 1

for k, p in enumerate(primes):
heapq.heappush(heap, (p, k))

for i in xrange(1, n):
uglies[i], k = heapq.heappop(heap)
ugly_by_last_prime[i] = k
idx[k] += 1
while ugly_by_last_prime[idx[k]] > k:
idx[k] += 1
heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

return uglies[-1]
```

Python:

```# Time:  O(n * k)
# Space: O(n + k)
# Hash solution. (932ms)
class Solution2(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
uglies, idx, heap, ugly_set = [0] * n, [0] * len(primes), [], set([1])
uglies[0] = 1

for k, p in enumerate(primes):
heapq.heappush(heap, (p, k))

for i in xrange(1, n):
uglies[i], k = heapq.heappop(heap)
while (primes[k] * uglies[idx[k]]) in ugly_set:
idx[k] += 1
heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

return uglies[-1]
```

Python:

```# Time:  O(n * logk) ~ O(n * klogk)
# Space: O(n + k)
class Solution3(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
uglies, idx, heap = [1], [0] * len(primes), []
for k, p in enumerate(primes):
heapq.heappush(heap, (p, k))

for i in xrange(1, n):
min_val, k = heap[0]
uglies += [min_val]

while heap[0][0] == min_val:  # worst time: O(klogk)
min_val, k = heapq.heappop(heap)
idx[k] += 1
heapq.heappush(heap, (primes[k] * uglies[idx[k]], k))

return uglies[-1]　　　　```

C++:

```class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> res(1, 1), idx(primes.size(), 0);
while (res.size() < n) {
vector<int> tmp;
int mn = INT_MAX;
for (int i = 0; i < primes.size(); ++i) {
tmp.push_back(res[idx[i]] * primes[i]);
}
for (int i = 0; i < primes.size(); ++i) {
mn = min(mn, tmp[i]);
}
for (int i = 0; i < primes.size(); ++i) {
if (mn == tmp[i]) ++idx[i];
}
res.push_back(mn);
}
return res.back();
}
};
```

C++:

```class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
vector<int> dp(n, 1), idx(primes.size(), 0);
for (int i = 1; i < n; ++i) {
dp[i] = INT_MAX;
for (int j = 0; j < primes.size(); ++j) {
dp[i] = min(dp[i], dp[idx[j]] * primes[j]);
}
for (int j = 0; j < primes.size(); ++j) {
if (dp[i] == dp[idx[j]] * primes[j]) {
++idx[j];
}
}
}
return dp.back();
}
};
```

[LeetCode] 263. Ugly Number 丑陋数

[LeetCode] 264. Ugly Number II 丑陋数 II