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

"tree"Copy

"eert"
Copy

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()
}Copy

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
}
Copy