原题
Given a list of words and an integer k, return the top k frequent words in the list.
给出
[
"yes", "lint", "code",
"yes", "code", "baby",
"you", "baby", "chrome",
"safari", "lint", "code",
"body", "lint", "code"
]
当k=3时，返回["code", "lint", "baby"]
当k=4时，返回["code", "lint", "baby", "yes"]
解题思路
- 首先使用hash table统计词频，建立一个存有（单词，词频）结构的数组
- 自定义（单词，词频）结构的比较方式
- 快速排序，然后取出前K个，得到结果
完整代码
class Solution:
# @param {string[]} words a list of string
# @param {int} k an integer
# @return {string[]} a list of string
def topKFrequentWords(self, words, k):
map = {}
for word in words:
if word not in map:
map[word] = 1
else:
map[word] += 1
temp = []
for key, value in map.items():
temp.append((value, key))
temp.sort(cmp=self.cmp)
result = []
for i in range(k):
result.append(temp[i][1])
return result
def cmp(self, a, b):
if a[0] > b[0] or a[0] == b[0] and a[1] < b[1]:
return -1
elif a[0] == b[0] and a[1] == b[1]:
return 0
else:
return 1
