- 前 K 个高频元素(难度 中等)
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
提示：
1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
题解一：堆
找出前K个高频元素 涉及到排序算法
为什么不用快排呢， 使用快排要将map转换为vector的结构，然后对整个数组进行排序， 而这种场景下，我们其实只需要维护k个有序的序列就可以了，所以使用优先级队列(就是一个披着队列外衣的堆)是最优的。
import heapq
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic={}
for i in range(len(nums)):
dic[nums[i]] = dic.get(nums[i],0) + 1
pri_que = [] #小根堆
for key,val in dic.items():
heapq.heappush(pri_que,(val,key))
if len(pri_que)>k: #大于k就pop出val值最小的
heapq.heappop(pri_que)
res=[0]*k
for i in range(len(pri_que)):
res[i]=pri_que[i][1]
return res
#内置函数写法
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = collections.Counter(nums)
heap = [(val, key) for key, val in count.items()]
return [item[1] for item in heapq.nlargest(k, heap)]
时间复杂度：O(Nlog(k+1))
空间复杂度：O(N)。哈希表的大小为 O(N)O(N)，而堆的大小为 O(k+1)，共计为 O(N)。
题解二： 直接排序
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = collections.Counter(nums)
return [item[0] for item in count.most_common(k)]
时间复杂度0(nlogn)
空间复杂度0(n)
