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 <= 10^5
• k的取值范围是[1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前k个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于O(n log n)，其中n是数组大小。

1.哈希+排序
Python解答：

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        adic = {}
        for item in nums:
            if item not in adic.keys():
                adic[item] = 1
            else:
                adic[item] += 1
        lis = list(adic.items())
        lis.sort(key=(lambda x: -x[1]))
        return [lis[i][0] for i in range(k)]

2.优先队列
Python解答：

import heapq
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        adic = {}
        for item in nums:
            if item not in adic.keys():
                adic[item] = 1
            else:
                adic[item] += 1
        res = []
        for key, value in adic.items():
            if len(res) < k:
                heapq.heappush(res, (value, key))
            else:
                heapq.heappushpop(res, (value, key))
        return [item[1] for item in res]