（12）Go实现的最小堆求前m个高频数字

leetcode-347: 前m个高频元素

算法思路：
（1）创建map[int]int，k为数值中元素，v表示出现的次数，用map去重；
（2）维护一个K个节点的最小堆，堆中存储k，v；
（3）遍历map取出k，v，若v大于堆中最小v，则替换堆中最小的k，v；
（4）之后取出堆中的k，则为前m个高频数字

最小二叉堆的实现：
type minHeap struct {
    size int
    nums [][2]int
}

func NewMinHeapTree() *minHeap {
    return &minHeap{}
}

func Parent(i int) int {
    if i == 0 {
        return 0
    }
    return (i - 1) / 2
}

func LeftChild(i int) int {
    return 2*i + 1
}

func (heap *minHeap) IsEmpty() bool {
    return heap.size == 0
}

func (heap *minHeap) GetSize() int {
    return heap.size
}

func (heap *minHeap) GetMinVal() ([2]int, error) {
    if heap.IsEmpty() {
        return [2]int{}, errors.New(
            "failed to geiMinVal,minHeap is empty.")
    }
    return heap.nums[0], nil
}

func siftDown(heap *minHeap, parI int) {
    var minI int
    for {
        leftI := LeftChild(parI)
        switch {
        case leftI+1 > heap.size:
            return
        case leftI+2 > heap.size:
            if heap.nums[parI][1] > heap.nums[leftI][1] {
                heap.nums[parI], heap.nums[leftI] = heap.nums[leftI],
                    heap.nums[parI]
            }
            return
        case heap.nums[leftI][1] <= heap.nums[leftI+1][1]:
            minI = leftI
        case heap.nums[leftI][1] > heap.nums[leftI+1][1]:
            minI = leftI + 1
        }

        if heap.nums[parI][1] > heap.nums[minI][1] {
            heap.nums[parI], heap.nums[minI] = heap.nums[minI],
                heap.nums[parI]
        }
        parI = minI
    }
}

func (heap *minHeap) SiftUp(key, val int) {
    heap.nums = append(heap.nums, [2]int{key, val})
    parI := Parent(heap.size)
    childI := heap.size

    for heap.nums[parI][1] > heap.nums[childI][1] {
        heap.nums[parI], heap.nums[childI] = heap.nums[childI],
            heap.nums[parI]
        childI = parI
        parI = Parent(parI)
    }
    heap.size++
}

func (heap *minHeap) SiftDown() ([2]int, error) {
    minVal, err := heap.GetMinVal()
    if err != nil {
        return minVal, err
    }

    heap.size--
    heap.nums[0], heap.nums[heap.size] = heap.nums[heap.size], [2]int{}

    siftDown(heap, 0)
    return minVal, nil
}

func (heap *minHeap) Replace(key, val int) ([2]int, error) {
    minVal, err := heap.GetMinVal()
    if err != nil {
        return minVal, err
    }
    heap.nums[0] = [2]int{key, val}

    siftDown(heap, 0)
    return minVal, nil
}

前m个高频数字的实现：
func topKFrequent(nums []int, k int) []int {
    h := NewMinHeapTree()
    m := make(map[int]int)
    for _, v := range nums {
        m[v]++
    }

    count := 0
    minVal := [2]int{}
    minV := 0
    for v1, v2 := range m {
        if count == k {
            if v2 > minV {
                h.Replace(v1, v2)
                minVal, _ = h.GetMinVal()
                minV = minVal[1]
            }
            continue
        }
        h.SiftUp(v1, v2)
        count++
        if count == k {
            minVal, _ = h.GetMinVal()
            minV = minVal[1]
        }
    }

    buf := []int{}
    for i := 0; i < k; i++ {
        v, _ := h.SiftDown()
        buf = append(buf, v[0])
    }
    return buf
}

通过，逻辑正确。

解决方法2，不用最小堆，速度或许更快点，参考leetcode上的最优解：
// 代码如下
func topKFrequent(nums []int, k int) []int {
    arr := make([]int, 0)
    if len(nums) == 0 {
        return arr
    }
    m := make(map[int]int)
    maxCount := 0
    for _, v := range nums {
        m[v] += 1
        if m[v] > maxCount {
            maxCount = m[v]
        }
    }
    tmp := make([][]int, maxCount+1)
    for k, v := range m {
        tmp[v] = append(tmp[v], k)
    }
    for i := maxCount; i >= 0; i-- {
        if len(tmp[i]) == 0 {
            continue
        }
        for _, v := range tmp[i] {
            arr = append(arr, v)
            if len(arr) == k {
                goto BREAK
            }
        }
    }
BREAK:
    return arr
}

相关问题：
求n个数字中前m个最大值：https://www.jianshu.com/p/29493ea46f7b

有bug欢迎指出

最后编辑于：2020.09.18 01:59:49