本文共 1123 字，大约阅读时间需要 3 分钟。

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2

输入: nums = [1], k = 1

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

解题思路

顾名思义，桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数（或其它属 性），然后对桶进行排序。针对样例来说，我们先通过桶排序得到三个桶[1,2,3,4]，它们的值分别 为[4,2,1,1]，表示每个数字出现的次数。

紧接着，我们对桶的频次进行排序，前k 大个桶即是前k 个频繁的数。这里我们可以使用各种 排序算法，甚至可以再进行一次桶排序，把每个旧桶根据频次放在不同的新桶内。针对样例来说， 因为目前最大的频次是 4，我们建立 [1,2,3,4] 四个新桶，它们分别放入的旧桶为 [ [3,4],[2],[],[1] ]， 表示不同数字出现的频率。

最后，我们从后往前遍历，直到找到 k 个旧桶。

AC

class Solution {
   public:    vector
   
     topKFrequent(vector
    
     & nums, int k) {
           unordered_map
     
       mp;        int max_count=0;        for(auto x:nums){
               ++mp[x];            if(max_count<=mp[x]) max_count=mp[x];        }        vector
      
       
        > v(max_count+1);        for(auto it:mp)            v[it.second].push_back(it.first);        vector
        
          ans; for(int i=max_count;i>=0;i--){ for(auto x:v[i]){ ans.push_back(x); if(ans.size()==k) break; } if(ans.size()==k) break; } return ans; }};
        
       
      
     
    
   

转载地址：https://chocolate.blog.csdn.net/article/details/106217895 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！