题目

给一非空的单词列表，返回前 k 个出现次数最多的单词。

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

示例 1：
输入: ["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. 假定 k 总为有效值， 1 ≤ k ≤ 集合元素数。
  2. 输入的单词均由小写字母组成。

方案一（两次稳定的排序算法）

  1. class Solution:
  2.     def topKFrequent(self, words: List[str], k: int) -> List[str]:
  3.         # 两次稳定的排序算法
  4.         words_count = []
  5.         words_mapping = {}  # key: word, value: words_count_index
  6.         for word in words:
  7.             if word in words_mapping:
  8.                 words_count[words_mapping[word]][1] += 1
  9.             else:
  10.                 words_count.append([word, 1])
  11.                 words_mapping[word] = len(words_count) - 1
  13.         words_count.sort(key=lambda t: t[0])
  14.         words_count.sort(key=lambda t: t[1], reverse=True)
  16.         return [word for word, count in words_count[:k]]

leetcode 写法

  1. class Solution(object):
  2.     def topKFrequent(self, words, k):
  3.         count = collections.Counter(words)
  4.         candidates = count.keys()
  5.         candidates.sort(key = lambda w: (-count[w], w))
  6.         return candidates[:k]

方案二（堆）

  1. class Solution(object):
  2.     def topKFrequent(self, words, k):
  3.         count = collections.Counter(words)
  4.         heap = [(-freq, word) for word, freq in count.items()]
  5.         heapq.heapify(heap)
  6.         return [heapq.heappop(heap)[1] for _ in xrange(k)]