willcool4ever

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

#include <iostream>
#include <set>
#include <map>
#include <vector>
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<int> v {1, 3, 3, 3, 1, 2, 1, 2, 6, 2, 4, 4, 4, 4};
    set<Data, MyComp> s;
    map<int, pair<int, int>> 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;
}

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

🔗