原题
给定一个数组，返回其出现次数最多的k个元素，时间复杂度优于O(nlogn)
样例
给出[1,1,1,2,2,3] 和 k = 2, 返回 [1,2]
解题思路
- 首先使用hash table统计元素的频率
- 建立一个长度为k的最小堆，因为堆顶最小，每次和堆顶元素作比较，大于堆顶就踢出堆顶元素并把当前元素加入堆中
完整代码
import Queue
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
map = {}
for num in nums:
if num not in map:
map[num] = 1
else:
map[num] += 1
minHeap = Queue.PriorityQueue()
for key, count in map.items():
if minHeap.qsize() < k:
minHeap.put((count, key))
elif minHeap.queue[0] < (count, key):
minHeap.get()
minHeap.put((count, key))
return [x[1] for x in minHeap.queue]
