当前位置：首页 > news >正文

347. 前 K 个高频元素（中等）

news 来源：原创 2024/9/20 3:15:00

347. 前 K 个高频元素

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

1. 题目描述

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

在这里插入图片描述

2.详细题解

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

Step1：初始化：统计各元素出现的频率，数据结构为字典，算法时间复杂度为 $O (n)$ ；
Step2：数组中元素个数为 $n$ ，构建 $n + 1$ 个桶，数据结构为数组，数组的索引下标对应元素出现的频率（可进一步优化，桶的数据为元素出现的最大频率）；
Step3：遍历各元素出现的频率，放入对应桶中，算法时间复杂度为 $O (m)$ ；
Step4：从右至左遍历桶，如果桶中有元素，则放入最终结果：
Step5：当结果数量为 $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。