go最大堆 实现字符串频率降序排列

用go内建堆容器实现大根堆

题面

给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
输入:

"tree"

输出:

"eert"

解释:
‘e’出现两次，’r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，”eetr”也是一个有效的答案。

大根堆

• 实现go 堆的 heap.Interface 接口
• 自定义依据重复次数实现最大堆排序规则

import (
    "bytes"
    "container/heap"
)

type ByteSliceHeap [][]byte
var _ heap.Interface = (*ByteSliceHeap)(nil)

func (h ByteSliceHeap) Len() int           { return len(h) }
func (h ByteSliceHeap) Less(i, j int) bool { return len(h[i]) > len(h[j]) }
func (h ByteSliceHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *ByteSliceHeap) Push(x interface{}) {
    *h = append(*h, x.([]byte))
}
func (h *ByteSliceHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func frequencySort(s string) string {
    m := make(map[byte][]byte, 0)
    for i := 0; i < len(s); i++ {
        if _, ok := m[s[i]]; !ok {
            m[s[i]] = []byte{s[i]}
        } else {
            m[s[i]] = append(m[s[i]], s[i])
        }
    }
    h := &ByteSliceHeap{}
    for _, v := range m {
        heap.Push(h, v)
    }
    buf := &bytes.Buffer{}
    for h.Len() > 0 {
        buf.Write(heap.Pop(h).([]byte))
    }
    return buf.String()
}

topk 小根堆

给定一个非空的整数数组，返回其中出现频率前 *k *高的元素

func topKFrequent(nums []int, k int) []int {
    occurrences := map[int]int{}
    for _, num := range nums {
        occurrences[num]++
    }
    h := &IHeap{}
    heap.Init(h)
    for key, value := range occurrences {
        heap.Push(h, [2]int{key, value})
        if h.Len() > k {
            heap.Pop(h)
        }
    }
    rs := make([]int, k)
    for i := 0; i < k; i++ {
        rs[k - i - 1] = heap.Pop(h).([2]int)[0]
    }
    return rs
}

type IHeap [][2]int

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
    *h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

本作品采用《CC 协议》，转载必须注明作者和本文链接