题目描述
超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
示例 1：
输入：n = 12, primes = [2,7,13,19]
输出：32
解释：给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
示例 2：
输入：n = 1, primes = [2,3,5]
输出：1
解释：1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。
提示：
1 <= n <= 1051 <= primes.length <= 1002 <= primes[i] <= 1000- 题目数据 保证
primes[i] 是一个质数 primes 中的所有值都 互不相同 ，且按 递增顺序 排列
解法
方法一：优先队列（小根堆）
思考
超级丑数只含给定质因子。若从小到大枚举正整数并试除，当 \(n\) 很大时线性扫描过慢。
从 \(1\) 出发，每次弹出堆顶 \(x\)，再把 \(x\times p\) 压回（防止溢出）。遇 \(x\) 能被当前 \(p\) 整除则停止后续质数，相当于欧拉筛去重。弹出 \(n\) 次即为第 \(n\) 个。
我们用一个优先队列（小根堆）维护所有可能的超级丑数，初始时将 \(1\) 放入队列中。
每次从队列中取出最小的超级丑数 \(x\)，将 \(x\) 乘以数组 primes 中的每个数，将乘积放入队列中，然后重复上述操作 \(n\) 次即可得到第 \(n\) 个超级丑数。
由于题目保证第 \(n\) 个超级丑数在 \(32\) 位带符号整数范围内，因此，我们将乘积放入队列之前，可以先判断乘积是否超过 \(2^{31} - 1\)，如果超过，则不需要将乘积放入队列中。另外，可以使用欧拉筛优化。
时间复杂度 \(O(n \times m \times \log (n \times m))\)，空间复杂度 \(O(n \times m)\)。其中 \(m\) 和 \(n\) 分别为数组 primes 的长度和给定的整数 \(n\)。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:
q = [1]
x = 0
mx = (1 << 31) - 1
for _ in range(n):
x = heappop(q)
for k in primes:
if x <= mx // k:
heappush(q, k * x)
if x % k == 0:
break
return x
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
PriorityQueue<Integer> q = new PriorityQueue<>();
q.offer(1);
int x = 0;
while (n-- > 0) {
x = q.poll();
while (!q.isEmpty() && q.peek() == x) {
q.poll();
}
for (int k : primes) {
if (k <= Integer.MAX_VALUE / x) {
q.offer(k * x);
}
if (x % k == 0) {
break;
}
}
}
return x;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 | class Solution {
public:
int nthSuperUglyNumber(int n, vector<int>& primes) {
priority_queue<int, vector<int>, greater<int>> q;
q.push(1);
int x = 0;
while (n--) {
x = q.top();
q.pop();
for (int& k : primes) {
if (x <= INT_MAX / k) {
q.push(k * x);
}
if (x % k == 0) {
break;
}
}
}
return x;
}
};
|
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 | func nthSuperUglyNumber(n int, primes []int) (x int) {
q := hp{[]int{1}}
for n > 0 {
n--
x = heap.Pop(&q).(int)
for _, k := range primes {
if x <= math.MaxInt32/k {
heap.Push(&q, k*x)
}
if x%k == 0 {
break
}
}
}
return
}
type hp struct{ sort.IntSlice }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
|
方法二：动态规划 + 多指针堆
思考
方法一对每个已生成丑数向所有质数扩展，堆中候选过多。改为每个质数只保留一条指针：堆顶给出当前最小候选，写入后再把该质数的下一倍数压回。候选规模降为 \(O(m)\)，时间 \(O(n\log m)\)。
用数组 \(ugly[1..n]\) 存放前 \(n\) 个超级丑数，并维护一个小根堆。堆中每个元素对应一个质数 \(p\)，记录当前应由 \(p\) 乘以第 \(\textit{index}\) 个超级丑数得到的候选值。
初始时 \(ugly[1] = 1\)，把每个质数 \(p\) 以 \((p, p, 2)\) 入堆。每次取出堆顶最小值写入 \(ugly\)，再把该质数的指针后移并压回堆中。这样每个质数只维护一条指针，避免方法一中对已生成丑数的全局扩展。
时间复杂度 \(O(n \times \log m)\)，空间复杂度 \(O(n + m)\)。其中 \(m\) 为数组 \(\textit{primes}\) 的长度。
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 | type Ugly struct{ value, prime, index int }
type Queue []Ugly
func (u Queue) Len() int { return len(u) }
func (u Queue) Swap(i, j int) { u[i], u[j] = u[j], u[i] }
func (u Queue) Less(i, j int) bool { return u[i].value < u[j].value }
func (u *Queue) Push(v any) { *u = append(*u, v.(Ugly)) }
func (u *Queue) Pop() any {
old, x := *u, (*u)[len(*u)-1]
*u = old[:len(old)-1]
return x
}
func nthSuperUglyNumber(n int, primes []int) int {
ugly, pq, p := make([]int, n+1), &Queue{}, 2
ugly[1] = 1
heap.Init(pq)
for _, v := range primes {
heap.Push(pq, Ugly{value: v, prime: v, index: 2})
}
for p <= n {
top := heap.Pop(pq).(Ugly)
if ugly[p-1] != top.value {
ugly[p], p = top.value, p+1
}
top.value, top.index = ugly[top.index]*top.prime, top.index+1
heap.Push(pq, top)
}
return ugly[n]
}
|