算法复习：桶排序

leetcode 347. 前 K 个高频元素

解决思路是使用桶排序，可以用map简化过程，map的特性是可以以key值作为索引，索引值可以存储key值的个数。

需要解决的问题是map只能自动按照key值排序，不能按照索引值排序，那么需要vector套在pair外面做一个壳为索引值做一次快排

#include<map>
#include<algorithm>
bool cmp(pair<int,int>a,pair<int,int>b)//从大到小
{
    return a.second>b.second;
}
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        map<int,int>donser;
        vector<int>result;
        for(int i=0;i<nums.size();i++)
            donser[nums[i]]++;
        vector<pair<int,int> >vec;
        for(map<int,int>::iterator it=donser.begin();it!=donser.end();it++)
            vec.push_back(pair<int,int>(it->first,it->second));
        sort(vec.begin(),vec.end(),cmp);
        for(int i=0;i<k;i++)
            result.push_back(vec[i].first);
        return result;
    }
};

#include<map>
#include<algorithm>
bool cmp(pair<int,int>a,pair<int,int>b)//从大到小
{
    return a.second>b.second;
}
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) 
    {
        map<int,int>donser;
        vector<int>result;
        for(int i=0;i<nums.size();i++)
            donser[nums[i]]++;
        vector<pair<int,int> >vec;
        for(map<int,int>::iterator it=donser.begin();it!=donser.end();it++)
            vec.push_back(pair<int,int>(it->first,it->second));
        sort(vec.begin(),vec.end(),cmp);
        for(int i=0;i<k;i++)
            result.push_back(vec[i].first);
        return result;
    }
};

leetcode 347