LeetCode 347. Top K Frequent Elements

题目

Given a non-empty array of integers, return the k most frequent elements.

For example:
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

分析

返回数组中的前 k 个最频繁的元素

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import heapq
# Uses a dict to maintain counts, heapifys the list of counts, then selects K elements out of the max heap.
# O(n + klogn)
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
freq = {}
freq_list=[]
for num in nums:
if num in freq:
freq[num] = freq[num] + 1
else:
freq[num] = 1
for key in freq.keys():
freq_list.append((-freq[key], key))
heapq.heapify(freq_list)
topk = []
for i in range(0,k):
topk.append(heapq.heappop(freq_list)[1])
return topk

点评

堆排序的实现和复杂度分析????