организовать по частоте - PullRequest
Новая
       62

организовать по частоте

0 голосов
/ 25 января 2019

Задача: спроектировать функцию так, чтобы она сначала возвращала отсортированную векторную пару с элементом наивысшей частоты, а если два элемента имеют одинаковую частоту, расположите их в отсортированном порядке (увеличивая) по элементам.

Имеется ли какая-либо концептуальная ошибка?

Можно ли еще больше уменьшить его сложность

в:

1 2 4 8 4 9 2 0 9 4 2
выход: частота частоты
2 3 4 3 9 2 0 1 1 1 8 1

len (v):

10 ^ 6
v [i]:
10 ^ 15 
#include <bits/stdc++.h>
using namespace std;

// sort function
bool mySort(pair<long long,long long> &a, pair<long long,long long>&b){
    if(a.second==b.second)
        return (a.first<b.first);
    else
        return (a.second>b.second);
}


vector<pair<long long, long long> > sortWithFrequency(vector<long long> v){

    vector<pair<long long, long long> > v_new;
    map<long long, long long> m;
    vector<long long>::iterator p= v.begin();


    while(p!=v.end()){
        m[*p]+=1;
        p++;
    }

   map<long long, long long>::iterator mp = m.begin();

    while(mp!=m.end()){
        v_new.push_back(pair<long long,long long>((*mp).first,(*mp).second));
        mp++;
    }

    sort(v_new.begin(), v_new.end(), mySort);

    return v_new;  
}

int main() {

    long long testcase;
    cin>>testcase;

    while(testcase--){
        long long N;
        cin >> N;

        // declaring vector
        vector<long long> v;

        for(long long i = 0;i<N;i++){
            long long k;
            cin >> k;
            v.push_back(k);
        }

    // calling function to perform required operation
        vector<pair<long long, long long> > v_new = sortWithFrequency(v);
        vector<pair<long long, long long> >::iterator it;

        for(it = v_new.begin();it!=v_new.end();it++){
            cout << it->first << " " << it->second << " ";
        }
        cout << endl;

    }


    return 0;
}

1 Ответ

0 голосов
/ 25 января 2019

мультикарта может уменьшить использование памяти: 

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

int main() {

    std::vector<int> v = { 1, 2, 4, 8, 4, 9, 2, 0, 9, 4, 2 };
    std::for_each(v.begin(), v.end(), [](int i) { std::cout << i << " "; });
    std::cout << std::endl;

    std::map<int, size_t> m;
    std::multimap<size_t, int> mm;
    std::for_each(v.begin(), v.end(), [&](int i) { m[i]++; });
    std::for_each(m.begin(), m.end(), [&](std::pair<int, size_t> p) { mm.insert(std::pair<size_t, int>(p.second, p.first)); });
    std::for_each(mm.rbegin(), mm.rend(), [](std::pair<size_t, int> p) { std::cout << p.second << " " << p.first << " "; });
    std::cout << std::endl;

    return 0;
}
...