## 题目描述：

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.

## 题目大意：

(1) 1 被认为是超级丑陋数，无论给定怎样的质数列表.

(2) 给定的质数列表以升序排列.

(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

## Java代码：

``````public class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int size = primes.length;
int q[] = new int[n];
int idxes[] = new int[size];
int vals[] = new int[size];
q[0] = 1;
for (int i = 1; i < n; i++) {
for (int j = 0; j < size; j++) {
vals[j] = q[idxes[j]] * primes[j];
}
q[i] = findMin(vals);
for (int j = 0; j < size; j++) {
if (vals[j] == q[i]) {
idxes[j] += 1;
}
}
}
return q[n - 1];
}

public int findMin(int[] nums) {
int min = nums[0];
for (int i = 1; i < nums.length; i++) {
min = Math.min(min, nums[i]);
}
return min;
}

}``````

## Python代码：

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

## Python代码（4行版本）：

``````class Solution(object):
def nthSuperUglyNumber(self, n, primes):
"""
:type n: int
:type primes: List[int]
:rtype: int
"""
uglies = [1]
merged = heapq.merge(*map(lambda p: (u*p for u in uglies), primes))
uniqed = (u for u, _ in itertools.groupby(merged))
map(uglies.append, itertools.islice(uniqed, n-1))
return uglies[-1]
``````

Pingbacks已关闭。