题目
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
思路
当使用频率最高的元素前k个作为题目的要求时，可以使用哈希表和堆的数据结构来解决。下面是哈希表解决方案。
- 首先创建一个哈希表
val_times，用于存储每个元素出现的次数。然后，遍历给定的列表nums，将每个元素作为键，初始次数为0，存入哈希表中。接着，再次遍历nums，将对应元素在哈希表中的次数加1。 - 为了找出出现次数最多的前k个元素，我们需要将次数转化为负数，并使用最小堆来维护前k个最大的次数。首先，将哈希表中所有次数取反并存入一个列表
times中。然后，使用heapify方法将times转化为最小堆。 - 接下来，我们创建一个空列表
times_list用于存储前k个最大次数（即堆中最小的k个元素）。通过循环k次，每次从堆中弹出一个元素并将其加入times_list中。 - 最后，我们需要根据最大次数找到对应的元素值。遍历
times_list，对于每个次数，再次遍历val_times，找到对应次数的元素值，并将其加入结果列表ret_list中。为了避免重复使用相同的元素，我们将已经使用过的元素在哈希表中标记为'used'。 - 最终，返回结果列表
ret_list即为出现次数最多的前k个元素。
详细解析链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
python代码
class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:val_times = {}#初始化val_timesfor i in nums:val_times[i] = 0for i in nums:val_times[i]+=1#求排在前k名的timestimes = list(val_times.values())for i in range(len(times)):times[i] = -times[i]heapify(times)times_list = []ret_list = []for i in range(k): times_list.append(-heappop(times))# 找出times对应的valsfor time in times_list:for val,tm in val_times.items():if time == tm and time != 'used': ret_list.append(val)val_times[val] = 'used' #标记用过的vals，防止重复breakreturn ret_list性能分析
- 时间复杂度：建立哈希表的时间复杂度为O(n)，堆的构建时间复杂度为O(klogk)，遍历哈希表的时间复杂度为O(n+k)，因此总体时间复杂度为O(n+klogk)。
- 空间复杂度：哈希表和堆分别需要O(n)和O(k)的空间，因此总体空间复杂度为O(n+k)。
示例和测试： 假设输入数组为[1, 1, 1, 2, 2, 3]，k为2，则输出结果应为[1, 2]。
总结
总结： 本文介绍了一种使用哈希表和堆来找出出现频率最高的前k个元素的解决方案。该方案在时间和空间复杂度上都具有较好的表现，适用于需要高效解决类似问题的场景。同时，在实际应用中，可以根据具体需求对算法进行相应的优化和拓展。
希望本文能够帮助你更好地理解并应用哈希表和堆这两种数据结构，并提高解决类似问题的能力。
