算法：
topk问题，解决的办法通常都是使用最小堆或者最大堆。
大顶堆：父亲节点的值总是比其两个子节点的值大。
小顶堆：父亲节点的值总是比其两个子节点的值小。
对于大顶堆：arr[i]>=arr[2*i+1] && arr[i] >= arr[2*i+2]
对于小顶堆：arr[i]<=arr[2*i+1] && arr[i] <= arr[2*i+2]
备注：除此之外，我们还可以使用golang中的sort()函数，将数组排序，
然后取出来前k个元素即可。
题目1：
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/
代码实现：
/*
解题思路：
1.先根据数组前k个元素，建一个k大小的大顶堆
2.将数组剩余的len-k个元素依次放入大顶堆中，
当元素小于大顶堆最大的数值的时候，进堆；
当元素大于堆的最大值的时候，跳过。
*/
func getLeastNumbers(arr []int, k int) []int {
if k > len(arr) || k == 0{
return nil
}
if k == len(arr) {
return arr
}
maxH := buildHeap(arr[:k])
for i := k; i<len(arr); i++ {
if arr[i] < maxH[0] {
maxH[0] = arr[i]
maxH = buildHeap(maxH)
}
}
return maxH
}
func buildHeap(arr []int) []int {
len := len(arr) - 1
minP := (len -1)/2 // 找到最底层的根节点
for minP >= 0 {
heapify(arr,minP) // 从最低的那个父节点开始调整
minP--
}
return arr
}
func heapify(arr []int, i int) {
len := len(arr)
if i >= len {
return
}
l,r := 2*i+1,2*i+2
// 找到父节点，两个子节点中的最大的那个值，调整这个元素为父节点
max := i
if l < len && arr[l]>arr[max] {
max = l
}
if r < len && arr[r]>arr[max] {
max = r
}
// 继续调整这个父节点的子孙节点，让他们也是大顶堆
if max != i {
arr[max],arr[i] = arr[i], arr[max]
heapify(arr,max)
}
}
执行结果：
题目2:
https://leetcode-cn.com/problems/top-k-frequent-elements/
代码实现：
type Node struct{
Key int
Value int
}
func topKFrequent(nums []int, k int) []int {
// 1.通过map去重，并对每一个元素计数，统计出现频率
tmpM := make(map[int]int)
for _,n := range nums {
if _,ok := tmpM[n]; !ok {
tmpM[n] = 1
} else {
tmpM[n]++
}
}
// 2.将map里面去重后的数据放到队列里面，这因为map是无序的
res := []Node{}
for k,v:=range tmpM{
res = append(res,Node{k,v})
}
// 3.对于小于k的数组的处理，这里就转换成了题目1中的topk问题
r := []int{}
if len(res) <=k {
for i:= 0; i< k; i++ {
r = append(r,res[i].Key)
}
return r
}
// 4.建立一个k个元素的最小堆
heap := res[:k] // 注意：需要额外的一个数组来存储堆的数据
buildMinHeap(heap)
for i:=k; i< len(res);i++ {
if res[i].Value>heap[0].Value {
heap[0].Key = res[i].Key
heap[0].Value = res[i].Value
heapify(heap,0)
}
}
// 5.对这些数据按照从小到大顺序排序
for i:= k-1; i>=0; i-- {
r = append(r,heap[i].Key)
}
return r
}
func buildMinHeap(nums []Node) {
for startIdx := (len(nums)-1)/2; startIdx >=0;startIdx-- {
// 最后的一个父亲节点开始，最后一个父亲节点的子节点是叶子节点
heapify(nums,startIdx)
}
}
func heapify(nums []Node , i int) { // 最大K用，最小堆
l := len(nums)
if l <= i {
return
}
left,right := 2*i +1, 2*i +2
max := i
if left <l &&nums[left].Value<nums[max].Value {
max = left
}
if right <l && nums[right].Value<nums[max].Value {
max = right
}
if max != i {
// 交换元素的时候，记得将Node中的所有值都做交换
nums[max].Key,nums[i].Key = nums[i].Key,nums[max].Key
nums[max].Value,nums[i].Value = nums[i].Value,nums[max].Value
heapify(nums,max)
}
}
执行结果：
题目3:
https://leetcode-cn.com/problems/top-k-frequent-words/
代码实现：
func topKFrequent(words []string, k int) []string {
if len(words) <= k {
sort.Strings(words)
return words
}
// 1. 利用map去重，并记录高频单词
strM := make(map[string]int)
for _,w := range words {
_,ok := strM[w]
if ok == false {
strM[w] = 1
} else {
strM[w]++
}
}
// 2. 利用 Go的库函数sort()来实现排序
strN := Nodes{}
for k,v := range strM {
strN = append(strN,Node{Key:k,Value:v})
}
sort.Sort(Nodes(strN))
fmt.Println(strN)
var res []string
for _, v:=range strN {
res = append(res,v.Key)
}
return res[:k]
}
type Node struct {
Key string
Value int
}
type Nodes []Node
func (n Nodes) Len() int {
return len(n)
}
func (n Nodes) Swap(i,j int) {
n[i],n[j] = n[j],n[i]
}
func (n Nodes) Less(i, j int) bool {
if n[i].Value > n[j].Value {
return true
}
if n[i].Value == n[j].Value {
if n[i].Key <= n[j].Key {
return true
}
}
return false
}
执行结果：
