// dp[i]: 第i个超级丑数
// 时间 O(nm), 空间O(n+m), 可在求最小里优化为多路归并,n 优化为 logn
func nthSuperUglyNumber(n int, primes []int) int {
dp := make([]int, n+1)
m := len(primes)
pointers := make([]int, m)
nums := make([]int, m)
for i := range nums {
nums[i] = 1
}
for i := 1; i <= n; i++ {
minNum := math.MaxInt64
for j := range pointers {
minNum = min(minNum, nums[j])
}
dp[i] = minNum
for j := range nums {
if nums[j] == minNum {
pointers[j]++
nums[j] = dp[pointers[j]] * primes[j]
}
}
}
return dp[n]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
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
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