[重新解答]百度笔试：数组按频次排列-白红宇

[重新解答]百度笔试：数组按频次排列

阅读量：4092 次

发布时间：2019-05-25

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

题意为从一个乱序数组中，将其中的整数按照出现的频次多少来排列（并且出现几次就排列几个），比如输入为[1,2,1,2,3,3,1,6,4,4,4,4]，那么输出就应该为[4,4,4,4,1,1,1,2,2,3,3,6]，其中，如果某两个数字的出现频次相同，那么就按照输入用例中的原顺序排列。
[原题链接]

#include 
   
    #include 
    
     #include 
     #include 
      
       using namespace std;struct Data{
       int key;    int count;    int order;    Data(int K, int C, int O): key(K), count(C), order(O) {
   }};struct MyComp{
       bool operator()(const Data d1, const Data d2) const    {
           if(d1.count != d2.count )        {
               return d1.count > d2.count ;        }        else        {
               return d1.order <= d2.order;        }    }};int main(int argc, const char **argv){
       vector
       
         v {
   1, 3, 3, 3, 1, 2, 1, 2, 6, 2, 4, 4, 4, 4};    set
        
          s; map
         
          > m; int order = 0; for(int &i : v) { auto it = m.insert(make_pair(i, make_pair(1, order++))); if(!it.second) { order--; ++(it.first->second.first); } } for(int &i : v) { s.insert(Data(i, m[i].first, m[i].second)); } for (auto it = s.begin(); it != s.end(); ++it) { // cout << it->key << "|" << it->count << "|" << it->order << endl; cout << it->key << endl; // 4 4 4 4 1 1 1 3 3 3 2 2 2 6 } return 0;}