无标题文章

347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.For example,Given [1,1,1,2,2,3] and k = 2, return [1,2].

解析：

很明显本题应该用到的是hashtable和heap等相关的数据结果，可选的有unordered_map用来统计array
里面每个元素出现的次数，接着依照次数进行排序得到topK个元素，可选的有优先队列、最小堆等，
也可以直接将map转换为vector，然后对vector进行排序。转换如下：
 vector<pair<int, int>> pv(begin(my_map), end(my_map)) 

实现部分如下：

方法1:使用了priority_queue
struct node
    {
          int x, y;
           friend bool operator < (node a, node b)
          {
                 return a.y < b.y; //结构体中，x的优先级高
          }
          node(int xx,int yy) {
              x = xx;
              y = yy;
          }
    };
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map <int,int> times;
        vector<int> res;
        for (int i = 0; i < nums.size(); i++) {
            if (times.count(nums[i]) > 0) times[nums[i]]++;
            else times[nums[i]] = 1;
        }
        priority_queue<node> pq;
        for (auto it = times.begin(); it != times.end(); it++) {
            struct node n1 =   node(it->first,it->second); 
            pq.push(n1);
        }
        for(int i = 0 ;i < k; i++) {
           res.push_back(pq.top().x);
           pq.pop();
        }
        return res;
    }

方法2：使用stl自带的函数nth_element是将前n个元素排序，同时除了第n个元素位置正确外其他的均不变
vector<int> topKFrequent(vector<int>& nums, int k) {     
    unordered_map<int, int> my_map;
    for_each (begin(nums), end(nums), [&my_map](int i){ my_map[i]++;});
    vector<pair<int, int>> pv(begin(my_map), end(my_map));    
    nth_element(begin(pv), begin(pv)+k, end(pv), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
    vector<int> result; 
    transform(begin(pv), begin(pv)+k,back_inserter(result), [](pair<int, int> a){return a.first;}); 
    return result;
 }

方法3：直接对vector进行排序
 map<int,int> myMap; 
struct CmpByValue { 
  bool operator()(const pair<int,int>& l, const pair<int,int>& r) 
  { 
    return l.second > r.second; 
  } 
};  //this Compair construct is used to sort the pair by pair.second().
vector<int> topKFrequent(vector<int>& nums, int k) {   
      for(auto i=nums.begin();i!=nums.end();i++) {   
          if(myMap.find(*i)!=myMap.end()) { 
               myMap[*i]++;
           } else { 
             myMap[*i]=1; 
           }
    } 
    vector<pair<int,int>> name_score_vec(myMap.begin(), myMap.end()); 
  //排序 vector<int> vec;    
    sort(name_score_vec.begin(), name_score_vec.end(), CmpByValue());
    for(int j=0;j<k;j++) { 
      vec.push_back(name_score_vec[j].first);
    } 
   return vec;
  }