题解 | #丑数#

package main

import (
    "container/heap"
)
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param index int整型 
 * @return int整型
*/
type IntHeap []int
func (h IntHeap) Len() int {
    return len(h)
}
func (h IntHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}
func (h IntHeap) Less(i, j int) bool {
    return h[i] < h[j]
}
func (h *IntHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
    x := (*h)[h.Len()-1]
    *h = (*h)[:h.Len()-1]
    return x
}

func GetUglyNumber_Solution( index int ) int {
    // write code here
    if index <= 6 {
        return index
    }
    // heap.Interface
    h := &IntHeap{1}
    // heap.Init(heap.Interface) 初始建堆
    heap.Init(h)
    factors := []int{2, 3, 5}
    exist := map[int]bool{1: true}
    for i := 0; i < index; i++ {
        // 小根堆弹出堆顶元素
        x := heap.Pop(h).(int)
        // 已经使用了，删除
        delete(exist, x)
        // 当 i == index-1，说明 x 就是第 index 个丑数（我们从 0 开始的）
        if i == index-1 {
            return x
        }
        for _, fac := range factors {
            // 如果这个丑数还没有被遍历到，那么入堆
            // 比如 x = 1 计算的三个新的堆元素分别为 2 3 5
            // 下一次弹出 x = 2 计算出的新的堆元素为 4 6 10
            // 再下一次弹出 3，计算出的新的堆元素为 6 9 15 和之前的 6 出现了重复，因此我们使用 map 就是为了去重的
            if _, ok := exist[x*fac]; !ok {
                heap.Push(h, x*fac)
                exist[x*fac] = true
            }
        }
    }

    return 1
}