Top K Frequent Elements

1. 解析

题目大意，求前k个高频繁数(这k个数不能重复)，题目中已经明确表示 k <= 不同的数的个数，所以其他异常情况我们无需考虑。

2. 分析

题目的难点：如何根据它们出现的次数进行排序。我采取的方法比较极端，利用hashtable记录每一个数和它们出现的次数，由于hashtable没有提供根据value值进行排序的功能，所以我借助可以进行排序的vector容器，直接利用STL库提供的sort函数根据value的值进行排序，不多讲，详见代码，整体思想比较普通。以下的两种解法，我认为才是题目想考察的，分别利用堆排序和桶排序的思想，感谢@Grandyang提供的思路。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<pair<int, int>> array;
        map<int, int> exist;
        for (int num : nums) exist[num]++;
        array.insert(array.begin(), exist.begin(), exist.end());
        sort(array.begin(), array.end(), [](pair<int, int> a, pair<int, int> b) {return a.second > b.second;});
        vector<int> res;
        for (int i = 0; i < k; ++i) res.push_back(array[i].first);
        return res;
    }
};

3.  堆排序求解

STL库提供了优先队列priority_queue的结构，底层的实现就是heap，默认的情况下是max-heap。整体思想：利用hashtable存储下数和对应出现的次数，然后将数出现的次数作为key，数作为value放在优先队列当中，优先队列的堆顶存储的就是当前出现次数最多的元素，这就是我们想要的，取到第n个即可~~~

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k){ //堆排序
        vector<int> res;
        map<int, int> exist;
        priority_queue<pair<int, int>> frequent_num;
        for (int num : nums) exist[num]++;
        for (auto it : exist) frequent_num.push({it.second, it.first}); //将value作为键值
        while (! frequent_num.empty()){  
            res.push_back(frequent_num.top().second);
            if (res.size() == k) break;
            frequent_num.pop();
        }
        return res;
    }
};

4. 桶排序求解 

想法很巧妙，我之前了解过桶排序，但一直不是很清楚它是怎么应用的，在这里看到啦，哈哈~~~整体思想：将出现的次数作为筛选的桶，每个桶存储的就是出现次数相同的数，然后根据出现次数最多的桶开始，依次取它们存储的元素即可

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k){ //桶排序
        vector<int> res;
        vector<vector<int>> backets(nums.size() + 1);
        map<int, int> exist;
        for (int num : nums) exist[num]++;
        for (auto it : exist) backets[it.second].push_back(it.first); //将出现次数作为桶
        for (int i = backets.size() - 1; i >= 0; --i){ //从出现次数最多的桶开始取元素
            for (int j = 0; j < backets[i].size(); ++j){
                res.push_back(backets[i][j]);
                if (res.size() == k) return res;
            }
        }
        return res;
    }
};

 [1]https://www.cnblogs.com/grandyang/p/5454125.html