前K个高频单词

题目描述：

给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。

返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。

示例 1：

输入: words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2
输出: [“i”, “love”]
解析: “i” 和 “love” 为出现次数最多的两个单词，均为2次。
注意，按字母顺序 “i” 在 “love” 之前。
示例 2：

输入: [“the”, “day”, “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is”, “is”], k = 4
输出: [“the”, “is”, “sunny”, “day”]
解析: “the”, “is”, “sunny” 和 “day” 是出现次数最多的四个单词，
出现次数依次为 4, 3, 2 和 1 次。

注意：

1 <= words.length <= 500
1 <= words[i] <= 10
words[i] 由小写英文字母组成。
k 的取值范围是 [1, 不同 words[i] 的数量]

进阶：尝试以 O(n log k) 时间复杂度和 O(n) 空间复杂度解决。

思路:

时间复杂度：O(nlogk),空间复杂度O()

用堆排序，做到nlogk

代码:

type pair struct{
    s string
    c int
}

func topKFrequent(words []string, k int) []string {
    sort.Strings(words)
    fmt.Println(words)
    var pairs []pair
    pairs = append(pairs, pair{words[0], 1})
    for i:=1;i<len(words);i++{
        if words[i] == words[i-1]{
            pairs[len(pairs)-1].c++
        }else{
            pairs = append(pairs, pair{words[i], 1})
        }
    }
    //fmt.Println(pairs)
    return headsort(pairs, k)

}

func headsort(pairs []pair, k int)[]string{
    n := len(pairs)
    var res []string
    for i:=n/2; i>=0; i--{
        headsortMax(pairs, i,n)
    }
    //fmt.Println(pairs)
    res = append(res, pairs[0].s)
    pairs[0],pairs[n-1] = pairs[n-1], pairs[0]
    n--
    for i:=1;i<k;i++{
        headsortMax(pairs, 0,n)
        res = append(res, pairs[0].s)
        pairs[0],pairs[n-1] = pairs[n-1], pairs[0]
        n--
    }
    return res
}

func headsortMax (pairs []pair, i int,n int){
    maxi := i
    for{
        if i*2 <n && ((pairs[i*2].c > pairs[maxi].c) || (pairs[i*2].c == pairs[maxi].c && pairs[i*2].s < pairs[maxi].s)){
            maxi = i*2
        }
        if i*2+1<n && ((pairs[i*2+1].c > pairs[maxi].c) || (pairs[i*2+1].c == pairs[maxi].c && pairs[i*2+1].s < pairs[maxi].s)){
            maxi = i*2+1
        }

        if maxi != i{
            pairs[i],pairs[maxi] = pairs[maxi], pairs[i]
            i = maxi
        }else{
            break
        }
    }
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

代码效率：

执行用时：8 ms, 在所有 Go 提交中击败了20.87%的用户
内存消耗：4.3 MB, 在所有 Go 提交中击败了45.48%的用户