想啥呢，5000块钱就想贿赂字节面试官？

专栏：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算法文档 。