arrange by Frequency

Question

Task: design a function such that it returns a sorted vector pair with highest frequency element first and if two elements have same frequency, arrange them in sorted order(increasing) by element.

Does it have any conceptual error?

Is it possible to further decrease it's complexity

in:

1 2 4 8 4 9 2 0 9 4 2

out: number frequency

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;
}

Answer 1

multimap can decrease memory usage:

#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;
}

Answer 2

You have too many containers. You need basically only need 2.

And, there is a more or less standard approach for counting something in a container.

We can use an associative container like a std::map or a std::unordered_map. And here we associate a "key", in this case the input number to count, with a value, in this case the count of the specific input number.

And luckily the maps have a very nice index operator[]. This will look for the given key and if found, return a reference to the value. If not found, then it will create a new entry with the key and return a reference to the new entry. So, in both cases, we will get a reference to the value used for counting. And then we can simply write:

std::unordered_map<long long, unsigned int> counter{}; for (const auto& c : myData) counter[c]++;

And that looks really intuitive.

After this operation, you have already the frequency table. Either sorted, by using a std::map or unsorted, but faster accessible with a std::unordered_map.

The std::unordered_map will be a key factor here. It will be very fast because it uses hashes.

And, we can read the values from std::cin and directly do the counting. That will save memory.

To sort it, we copy the counter into a std::multiset with a custom sort operator. Then we get automatically what we want.

Please see below the optimized solution

#include <iostream>
#include <string>
#include <utility>
#include <set>
#include <unordered_map>
#include <vector>
#include <type_traits>

// ------------------------------------------------------------
// Create aliases. Save typing work and make code more readable
using Pair = std::pair<long long, unsigned int>;

// Standard approach for counter
using Counter = std::unordered_map<Pair::first_type, Pair::second_type>;

// Sorted values will be stored in a multiset
struct Comp { bool operator ()(const Pair& p1, const Pair& p2) const { return (p1.second == p2.second) ? p1.first<p2.first : p1.second>p2.second; } };
using Rank = std::multiset<Pair, Comp>;
// ------------------------------------------------------------

// Test / Driver Code
int main() {

    // Get number of test cases
    long long numberOfTestCases{}; std::cin >> numberOfTestCases;

    // Work on all test cases
    while (numberOfTestCases--) {

        // Read the number of elements that must be evaluated
        int numberOfElements; std::cin >> numberOfElements;

        // Define and initialize counter
        Counter counter{};

        // Read and count all elements
        while (numberOfElements--) {

            // Read value and count it immediately
            long long value; std::cin >> value;

            // Count
            counter[value]++;
        }
        // Sort
        Rank rank(counter.begin(), counter.end());

        // Output
        bool printBlank{ false };
        for (const auto& [number, count] : counter)
            std::cout << (std::exchange(printBlank, true) ? " " : "") << number << ' ' << count;
        std::cout << '\n';
    }
}