Сортировать массив пар по частоте встречаемости в C / C ++ - PullRequest
Новая
       10

Сортировать массив пар по частоте встречаемости в C / C ++

0 голосов
/ 03 апреля 2020

Здесь у меня есть два массива, одна строка и одно целое: 

S[]={"abc","abc","aa","a","aa","abc"}
A[]={  3,    2,   4,   5,  6,   7 }

Каждый элемент в S [] связан с соответствующим элементом в A [] (например: "ab c" - 3, «ab c» - 2 и т. Д.)

Я хочу отсортировать эти массивы по частоте появления S [i], например: 

Sorted arrays: S[]={"abc","abc","abc","aa","aa","a"}
               A[]={ 2,    3,    7,    4,   6,   5 }

Таким образом, S [] сортируется по частоте появления s [i], и если два элемента имеют одинаковую частоту, «меньший» элемент в алфавите идет первым.

И соответствующий a [] элемент должен сортироваться все чаще, если два элемента s [] совпадают.

Что я должен использовать, чтобы отсортировать их, объединить в пару или использовать карту, потому что я пытался использовать их, но я все еще застрял.

Любая идея с примером кода будет оценена.

Ответы [ 2 ]

0 голосов
/ 06 апреля 2020

Я бы сделал это в два этапа. Сначала я посчитал частоты (и для этого можно было бы использовать std::map или std::unordered_map. Затем я бы сделал сортировку, используя ее в качестве первичного ключа, а строки и связанный номер в качестве вторичного и третичного ключей. 

#include <vector>
#include <unordered_map>
#include <string>
#include <iostream>
#include <algorithm>
#include <iterator>

using T = std::pair<std::string, int>;

namespace std {
std::ostream &operator<<(std::ostream &os, T const &t) {
    return os << t.first << ", " << t.second;
}
}

int main() {

    std::vector<T> inputs {
        { "abc", 3 }, {"abc", 2}, { "aa", 4}, {"a", 5}, { "aa", 6 }, { "abc", 7 }
    };

    std::unordered_map<std::string, int> counts;

    // first count the frequencies:
    for (auto const & i : inputs)
        ++counts[i.first];

    // order by freq desc, first asc, num asc
    std::sort(inputs.begin(), inputs.end(),
        [&](T const& a, T const& b) {
            if (counts[b.first] < counts[a.first])
                return true;
            if (counts[a.first] < counts[b.first])
                return false;
            if (a.first < b.first)
                return true;
            if (b.first < a.first)
                return false;
            return a.second < b.second;
        });

    // Show the result:
    std::copy(inputs.begin(), inputs.end(), std::ostream_iterator<T>(std::cout, "\n"));
}
0 голосов
/ 04 апреля 2020 
using namespace std
struct ds_t{
    string s;
    vector<int>i;
    ds_t(string ts, int value){
        s = ts;
        i.push_back(value);
    }    
};

int main()
{
    char* s[] = {"abc","abc","aa","a","aa","abc"};
    int   A[] = {3,2,4,5,6,7};
    map<string, ds_t> mVar;
    map<string, ds_t>::iterator itr;

    for(int i = 0; i < sizeof(s)/sizeof(char*) ; i++)
    {
        itr = mVar.find(s[i]);
        if(itr == mVar.end())
        {
            struct ds_t vDs(s[i],A[i]);
            mVar.insert(make_pair(s[i], vDs));
        }
        else
        {
            itr->second.i.push_back(A[i]);
            std::sort(itr->second.i.begin(), itr->second.i.end());
        }
    }

    map<string, ds_t>::reverse_iterator ritr;
    for(ritr = mVar.rbegin() ; ritr != mVar.rend(); ++ritr)
    {
        for(int i=0;i<ritr->second.i.size();i++)
        {
            printf("%s %d\n",ritr->first.c_str(),ritr->second.i[i]);
        }
    }
    return 0;

}

...