专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
一网友下周要面试字节，问给面试官5000块钱能不能过。首先来说字节的面试官不可能就一个人，如果每个人都给5000，那也不少了，就算都给也不一定保证所有人都收，所以还是不要想一些歪门邪道的 ，提高自己的技能才是正道。
在说5000块钱对于字节面试官来说真的不算啥，徇私舞弊被发现是要被开除的，不可能为了5000块钱冒这么大风险。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第347：前 K 个高频元素。
问题描述
来源：LeetCode第347题
难度：中等
给你一个整数数组 nums 和一个整数 k ，请你返回其中 出现频率前 k 高的元素 。你可以按任意顺序返回答案。
示例1：
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例2：
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
1 <= nums.length <= 10^5
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的
问题分析
这题让找出出现频率前 k 高的元素，我们首先 计算数组中每个元素出现的频率，然后再查找出现频率最高的 k 个元素 即可。
这里使用 ，当堆中元素个数大于 k 的时候，就把堆顶元素给移除，也就是把频率低的给移除，保证堆中的 k 个元素都是频率最高的。
JAVA：
public int[] topKFrequent(int[] nums, int k) {
// 统计每个数字出现的频率
Map
mp = new HashMap<>(); for ( int num : nums) mp.put(num, mp.getOrDefault(num, 0) + 1); // 最小堆，根据频率排序 PriorityQueue< int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[ 1])); for ( int key : mp.keySet()) { pq.add( new int[]{key, mp.get(key)}); // 添加到堆中 if (pq.size() > k) // 超过 k 个，移除堆顶元素 pq.poll(); } //把堆中的元素转化为数组 int[] ans = new int[k]; int i = 0; while (!pq.isEmpty()) ans[i++] = pq.poll()[ 0]; return ans; }C++：
public:
vector
topKFrequent(vector
&nums, int k) { // 先统计数组中所有元素的频率 unordered_map
mp; for (int num: nums) mp[num]++; // 使用最小堆，根据频率排序，只能保存k个元素， auto comp = [](const pair
&a, const pair
&b) { return a.second > b.second; }; priority_queue int , int>, vector int, int>>, decltype (comp)> pq (comp); for ( auto &entry: mp) { pq.emplace(entry.first, entry.second); if (pq.size() > k) // 堆中元素超过 k 个，移除多余的 pq.pop(); // 移除堆顶元素。 } // 把堆中的元素转成vector vector< int> ans; while (!pq.empty()) { ans.push_back(pq.top().first); // 取出堆顶元素 pq.pop(); // 移除堆顶元素。 } return ans; }
Python：
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 统计每个数字出现的频率
count_map = Counter(nums)
# 最小堆，根据频率排序
min_heap = []
for key, freq in count_map.items():
heapq.heappush(min_heap, (freq, key))
if len(min_heap) > k:
heapq.heappop(min_heap)
# 把堆中的元素转化为数组
ans = [item[1] for item in min_heap]
return ans笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴