栈与队列篇：347. 前 K 个高频元素(难度 中等)_python 给你一个数组nums和一个值k,返回其中出现频率前k高的元素

347. 前 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
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#内置函数写法
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)]


1
2
3
4
5
6
7
8

时间复杂度：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)]
1
2
3
4

时间复杂度0(nlogn)
空间复杂度0(n)