qidao123.com技术社区-IT企服评测·应用市场

标题: 【leetcode100】前K个高频元素 [打印本页]
作者: 渣渣兔    时间: 2025-4-20 03:58
标题: 【leetcode100】前K个高频元素
1、题目形貌

给你一个整数数组 nums 和一个整数 k ，请你返回此中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1:
  1. <strong>输入: </strong>nums = [1,1,1,2,2,3], k = 2
  2. <strong>输出: </strong>[1,2]
复制代码
示例 2:
  1. <strong>输入: </strong>nums = [1], k = 1
  2. <strong>输出: </strong>[1]
复制代码
2、初始思绪

2.1 思绪

全分列，起首使用字典存储每个数字出现的次数，然后对字典按照出现次数进行排序后输出。
2.2 完备代码

  1. class Solution:
  2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
  3.         dic = {}
  4.         for num in nums:
  5.             if num in dic.keys():
  6.                 dic[num] += 1
  7.             else:
  8.                 dic[num] = 1
  9.         #print(dic)
  10.         dic = sorted(dic.items(), key = lambda x:x[1], reverse = True)
  11.         #print(dic)
  12.         ans = []
  13.         for i in range(k):
  14.             ans.append(dic[i][0])
  15.         return ans
复制代码
2.3 注意点！

（1）时间复杂度为O(nlog n)，不满足题目中要求你所设计算法的时间复杂度 必须 优于 O(n log n) ，此中 n 是数组大小。
（2）对字典存储数字出现次数把握不熟练，可以简化代码：
  1. dic = Counter(nums)
复制代码
3 优化算法1

3.1 思绪

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

  1. class Solution:
  2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
  3.         heap = []
  4.         dic = Counter(nums)
  5.         for num, count in dic.items():
  6.             heapq.heappush(heap, (count, num))
  7.             if len(heap) > k:
  8.                 heapq.heappop(heap)
  9.         return [heap[i][1] for i in range(len(heap))]
复制代码
 3.3 增补知识

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

 

4 优化算法2

4.1 思绪

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

  1. class Solution:
  2.     def topKFrequent(self, nums: List[int], k: int) -> List[int]:
  3.         dic = Counter(nums)
  4.         res = heapq.nlargest(k, dic.items(), key = lambda x:x[1])
  5.         return [res[i][0] for i in range(k)]
复制代码
 4.3 增补知识

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


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 qidao123.com技术社区-IT企服评测·应用市场 (https://dis.qidao123.com/) Powered by Discuz! X3.4