【leetcode100】前K个高频元素

1、题目描述

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

2、初始思路

2.1 思路

全排列，首先使用字典存储每个数字出现的次数，然后对字典按照出现次数进行排序后输出。

2.2 完整代码

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:dic = {}for num in nums:if num in dic.keys():dic[num] += 1else:dic[num] = 1#print(dic)dic = sorted(dic.items(), key = lambda x:x[1], reverse = True)#print(dic)ans = []for i in range(k):ans.append(dic[i][0])return ans

2.3 注意点！

（1）时间复杂度为O(nlog n)，不满足题目中要求你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

（2）对字典存储数字出现次数掌握不熟练，可以简化代码：

dic = Counter(nums)

3 优化算法1

3.1 思路

使用堆的前K个元素的思路进行求解，时间复杂度为O(nlog k)。

3.2 代码

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:heap = []dic = Counter(nums)for num, count in dic.items():heapq.heappush(heap, (count, num))if len(heap) > k:heapq.heappop(heap)return [heap[i][1] for i in range(len(heap))]

 3.3 补充知识

为更好地使用堆，本文对堆进行了整理，具体如下：

 

4 优化算法2

4.1 思路

使用heapq的函数heapq.nlargerst，时间复杂度为O(nlog k)。

4.2 代码

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:dic = Counter(nums)res = heapq.nlargest(k, dic.items(), key = lambda x:x[1])return [res[i][0] for i in range(k)]

 4.3 补充知识

heapq.nlargest(n, iterable) 用于从可迭代对象（如列表、元组等）中提取 前 n 个最大元素，返回一个包含这些元素的列表（按从大到小排列）。