topK算法——面试
题目：我现在有一个文件，把文件中出现单词频率最高的k个单词找出来，文件内容都是逗号分隔的单词
我用go语言写
abc.txt内容 "wang,jing,yu,shuai,ge,shuai,ge,j"
package main
import (
"fmt"
"io/ioutil"
"sort"
"strings"
)
func main() {
contents, err := ioutil.ReadFile("D:\\test1\\topK\\abc.txt")
if err != nil {
fmt.Println("无法读取文件:", err)
return
} else {
fmt.Printf("%s\n", contents)
}
k := 2
words := strings.Split(string(contents), ",")
// 存放map，频率
pl := make(map[string]int, 0)
for _, v := range words {
pl[v]++
}
// 去重后数组
qcWords := []string{}
for k, _ := range pl {
qcWords = append(qcWords, k)
}
sort.Slice(qcWords, func(i, j int) bool {
return pl[qcWords[i]] > pl[qcWords[j]]
})
for i := 0; i < len(pl) && i < k; i++ {
fmt.Printf("%v,%v", qcWords[i], pl[qcWords[i]])
}
}
到此结束
考察点：
- 打开文件的api
- strings.Split
- map 存储单词的频率
- 再做一个数组存储字符串（去重后的，可以直接从map的k拿）
- 最后对这个字符串排序，到了这里就有几个选择了，上方选择了sort.Slice函数，底层是快速排序
- 最后输出即可
别的方案：
- 利用堆排序，因为是求频率最高的k个单词，所以可以用大顶堆，但是之前百度的面试官告诉我应该用小顶堆，各位大佬知道为什么吗？
- 或者你可以用其他排序方法
类似资料：