您的位置:首页 > 新闻 > 会展 > 347. 前 K 个高频元素(中等)

347. 前 K 个高频元素(中等)

2025/2/25 9:48:42 来源:https://blog.csdn.net/weixin_38979465/article/details/140363423  浏览:    关键词:347. 前 K 个高频元素(中等)

347. 前 K 个高频元素

  • 1. 题目描述
  • 2.详细题解
  • 3.代码实现
    • 3.1 Python
    • 3.2 Java

1. 题目描述

题目中转:347. 前 K 个高频元素

在这里插入图片描述

2.详细题解

    寻找出现频率前 k k k高的元素,因此需要先统计各个元素出现的次数,该步骤时间复杂度为 O ( n ) O(n) O(n),再对各元素的出现频率进行排序,假定不同元素的个数为 m m m,该步骤的最佳时间复杂度为 O ( m l o g ( m ) ) O(mlog(m)) O(mlog(m)),如归并、堆排序等算法。
  这里介绍一种桶排序算法:桶排序(Bucket Sort)是一种排序算法,它通过将数据分散到有限数量的桶中,然后对每个桶中的数据单独进行排序,最后按照顺序将各个桶中的数据合并起来得到最终排序结果。简单的说,已知数据种类有限,逐一遍历数据并装入相应的桶中,仅需 O ( n ) O(n) O(n)时间复杂度即可完成数据排序。
  对于本题,先统计各元素出现的频率,再以元素的频率作为桶,将相应频率的元素放入指定桶中。具体算法如下:

  • Step1:初始化:统计各元素出现的频率,数据结构为字典,算法时间复杂度为 O ( n ) O(n) O(n)
  • Step2:数组中元素个数为 n n n,构建 n + 1 n+1 n+1个桶,数据结构为数组,数组的索引下标对应元素出现的频率(可进一步优化,桶的数据为元素出现的最大频率);
  • Step3:遍历各元素出现的频率,放入对应桶中,算法时间复杂度为 O ( m ) O(m) O(m)
  • Step4:从右至左遍历桶,如果桶中有元素,则放入最终结果:
  • Step5:当结果数量为 k k k时,程序结束;
  • Step8:返回结果。

3.代码实现

3.1 Python

class Solution:def topKFrequent(self, nums: List[int], k: int) -> List[int]:fre_dict = {}for num in nums:fre_dict[num] = fre_dict.get(num, 0) + 1res = [[] for _ in range(len(nums) + 1)]for key, value in fre_dict.items():res[value].append(key)ans = []for i in range(len(nums), 0, -1):if len(res[i]) > 0:ans.extend(res[i])if len(ans) == k:breakreturn ans

在这里插入图片描述

3.2 Java

class Solution {public int[] topKFrequent(int[] nums, int k) {int[] res = new int[k];HashMap<Integer, Integer> fre_dict = new HashMap();for (int num: nums){if (fre_dict.containsKey(num)){fre_dict.put(num, fre_dict.get(num)+1);}else {fre_dict.put(num, 1);}}List<Integer>[] list = new List[nums.length+1];for(int key : fre_dict.keySet()){// 获取出现的次数作为下标int i = fre_dict.get(key);if(list[i] == null){list[i] = new ArrayList();} list[i].add(key);}for (int i=list.length-1, j = 0; i>=0 && j < k; i--){if (list[i] == null) continue;for (int value: list[i]){res[j++] = value;}}return res;}
}

在这里插入图片描述

  执行用时不必过于纠结,对比可以发现,对于python和java完全相同的编写,java的时间一般是优于python的;至于编写的代码的执行用时击败多少对手,执行用时和网络环境、当前提交代码人数等均有关系,可以尝试完全相同的代码多次执行用时也不是完全相同,只要确保自己代码的算法时间复杂度满足相应要求即可,也可以通过点击分布图查看其它coder的code。

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com