题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例:
- 输入: n = 10
- 输出: 12
- 解释:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。n 不超过 1690。
注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/
解法一：最小堆
超时代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
func nthUglyNumber(n int) int {
q := &minHeap{}
heap.Push(q, 1)
prev := 0
for n > 0 {
cur := heap.Pop(q).(int)
if cur != prev {
prev = cur
n--
}
heap.Push(q, 2*cur)
heap.Push(q, 3*cur)
heap.Push(q, 5*cur)
}
return prev
}
|
通过代码：
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
33
34
35
36
37
38
|
type minHeap struct {
sort.IntSlice
}
func (hp *minHeap) Push(x interface{}) {
hp.IntSlice = append(hp.IntSlice, x.(int))
}
func (hp *minHeap) Pop() interface{} {
a := hp.IntSlice
ret := a[len(a)-1]
hp.IntSlice = a[:len(a)-1]
return ret
}
func nthUglyNumber(n int) int {
q, record := &minHeap{}, make(map[int]struct{})
heap.Push(q, 1)
record[1] = struct{}{}
var ans int
for n > 0 {
ans = heap.Pop(q).(int)
n--
if _, has := record[2*ans]; !has {
heap.Push(q, 2*ans)
record[2*ans] = struct{}{}
}
if _, has := record[3*ans]; !has {
heap.Push(q, 3*ans)
record[3*ans] = struct{}{}
}
if _, has := record[5*ans]; !has {
heap.Push(q, 5*ans)
record[5*ans] = struct{}{}
}
}
return ans
}
|
另一种实现代码：
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
33
|
type MinHeap struct {
sort.IntSlice
}
func (m *MinHeap) Push(x interface{}) {
m.IntSlice = append(m.IntSlice, x.(int))
}
func (m *MinHeap) Pop() interface{} {
old := m.IntSlice
val := old[len(old)-1]
m.IntSlice = old[:len(old)-1]
return val
}
func nthUglyNumber(n int) int {
h, m := &MinHeap{}, make(map[int]bool)
heap.Push(h, 1)
m[1] = true
n--
for n > 0 {
cur := heap.Pop(h).(int)
for _, val := range []int{2, 3, 5} {
next := cur * val
if !m[next] {
m[next] = true
heap.Push(h, next)
}
}
n--
}
return heap.Pop(h).(int)
}
|
解法二：动态规划
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
|
func min(nums ...int) int {
res := nums[0]
for _, val := range nums {
if val < res {
res = val
}
}
return res
}
func nthUglyNumber(n int) int {
dp := make([]int, n+1)
a, b, c := 1, 1, 1
dp[1] = 1
for i := 2; i <= n; i++ {
dp[i] = min(dp[a]*2, dp[b]*3, dp[c]*5)
if dp[i] == dp[a]*2 {
a++
}
if dp[i] == dp[b]*3 {
b++
}
if dp[i] == dp[c]*5 {
c++
}
}
return dp[n]
}
|
