...
| Code Block |
|---|
|
func nthSuperUglyNumber(n int, primes []int) int {
h_ := make(IntHeap, 0, n)
h := &h_
heap.Push(h, 1)
num := -1
exists := make(map[int]struct{})
for i := 0; i < n; i++ {
num = heap.Pop(h).(int)
for _, p := range primes {
nn := num * p
if nn < num || nn > math.MaxInt32 {
continue
}
if _, exist := exists[nn]; exist {
continue
}
exists[nn] = struct{}{}
heap.Push(h, nn)
}
}
return num
}
// An IntHeap is a min-heap of ints.
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x any) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
|
...
不使用 map 去重 - 而是使用合并 k 个有序链表（丑数 II）的思路
| Code Block |
|---|
|
func nthSuperUglyNumber(n int, primes []int) int {
h_ := make(Heap, 0, n)
h := &h_
for _, p := range primes {
heap.Push(h, [3]int{1, p, 0})
}
uglys := make([]int, 1, n)
uglys[0] = 1
for len(uglys) < n {
top := heap.Pop(h).([3]int)
num, p, pi := top[0], top[1], top[2]
if num != uglys[len(uglys) - 1] {
uglys = append(uglys, num)
}
heap.Push(h, [3]int{p * uglys[pi], p, pi+1})
}
return uglys[n-1]
}
type Heap [][3]int
func (h Heap) Len() int { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x any) {
*h = append(*h, x.([3]int))
}
func (h *Heap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
|
LC 1201. 丑数 III
https://leetcode.com/problems/ugly-number-iii/
合并有序链表解法 (TLE)
| Code Block |
|---|
|
func nthUglyNumber(n int, a int, b int, c int) int {
h := &Heap{}
heap.Push(h, [2]int{a, a})
heap.Push(h, [2]int{b, b})
heap.Push(h, [2]int{c, c})
i := 0
num := 0
for i < n {
top := heap.Pop(h).([2]int)
v, factor := top[0], top[1]
if v != num {
num = v
i++
}
heap.Push(h, [2]int{v + factor, factor})
}
return num
}
type Heap [][2]int
func (h Heap) Len() int { return len(h) }
func (h Heap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h Heap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *Heap) Push(x any) {
*h = append(*h, x.([2]int))
}
func (h *Heap) Pop() any {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
} |
二分 + 集合解法