leetcode_692

淳属虚构 · · 72 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

Golang:

思路:topK问题,这题使用了堆

代码如下:

type NodeW struct {
    word string
    fre int
}
func topKFrequent2(words []string, k int) []string {
    mp:=make(map[string]int)
    for _,v:=range words{
        mp[v]++
    }
    var nodes []*NodeW
    for k,v:=range mp{
        node:=NodeW{
            word:k,
            fre:v,
        }
        nodes=append(nodes,&node)
    }
    buildMinHeapK(nodes[:k])
    for i:=k;i<len(nodes);i++{
        if nodes[i].fre>nodes[0].fre||(nodes[i].fre==nodes[0].fre&&strings.Compare(nodes[i].word,nodes[0].word)==-1){
            nodes[0]=nodes[i]
            adjustMinHeapK(nodes,0,k)
        }
    }
    var res []string
    for i:=k-1;i>=0;i--{
        res=append([]string{nodes[0].word},res...)
        nodes[0]=nodes[i]
        adjustMinHeapK(nodes,0,i)
    }
    return res
}
func buildMinHeapK(arr []*NodeW)  {
    for i:=len(arr)/2-1; i>=0; i-- {
        adjustMinHeapK(arr,i,len(arr))
    }
}
func adjustMinHeapK(arr []*NodeW,i int,length int)  {
    for k:=2*i+1; k<length; k=2*k+1 {
        if k+1<length&&(arr[k].fre>arr[k+1].fre||(arr[k].fre==arr[k+1].fre&&strings.Compare(arr[k+1].word,arr[k].word)!=-1)) {
            k=k+1
        }
        if arr[k].fre<arr[i].fre || (arr[k].fre==arr[i].fre&&strings.Compare(arr[k].word,arr[i].word)!=-1){
            arr[k],arr[i]=arr[i],arr[k]
            i=k
        }else {
            break
        }
    }
}

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:淳属虚构

查看原文:leetcode_692

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

72 次点击  
加入收藏 微博
上一篇:leetcode_725
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传