题解 | #丑数#

package main

import "container/heap"

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 interface{}) {
    *h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

/**
 * 
 * @param index int整型 
 * @return int整型
*/
func GetUglyNumber_Solution( index int ) int {
    if index==0{
        return 0
    }
    h := &IntHeap{1}
    heap.Init(h)
    factors:=[]int{2,3,5}
    vis:=map[int]bool{1:true}
    for i:=1;;i++{
        x:=heap.Pop(h).(int)
        delete(vis,x)
        if i==index{
            return x
        }
        for _,fa:=range factors{
            if _,ok:=vis[x*fa];!ok{
                heap.Push(h,x*fa)
                vis[x*fa]=true
            }
        }
    }
    return 1
}