C++ Find Top K most Frequent elements in sorted Vector using Pair Template

Hello Everyone!

In this tutorial, we will learn about Finding the top k most frequent elements in a sorted Vector, in the C++ programming language.

To understand the basic functionality of the Pair Template, we will recommend you visit, C++ STL Pair Template, where we have explained this concept in detail from scratch.

For a better understanding of its implementation, refer to the well-commented C++ code given below.

Code:

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

vector<int> topKFrequent(vector<int> &a, int k)
{
    unordered_map<int, int> u;

    int n = a.size();
    int i;

    for (i = 0; i < n; i++)
    {
        u[a[i]]++;
    }

    vector<pair<int, int>> v(u.begin(), u.end());

    sort(v.begin(), v.end(), [](pair<int, int> x, pair<int, int> y) {
        if (x.second == y.second)
            return x.first < y.first;
        else
            return x.second > y.second;
    });

    vector<int> r;
    for (i = 0; i < k; i++)
    {
        r.push_back(v[i].first);
    }

    return r;
}

int main()
{
    cout << "\n\nWelcome to Studytonight :-)\n\n\n";
    cout << " =====  Program to find the top k most frequent elements in a vector, in CPP  ===== \n\n\n";

    //initializing vector with the following elements
    vector<int> v = {1, 2, 3, 1, 2, 1};

    vector<int> f;

    int k = 2; //to find the 2 most frequent numbers

    int n = v.size();

    cout << "The elements of the given vector is : ";

    for (int i = 0; i < n; i++)
    {
        cout << v[i] << "  ";
    }

    f = topKFrequent(v, k);

    n = f.size();

    cout << "\n\n The top " << k << " most frequent numbers are: ";

    for (int i = 0; i < n; i++)
    {
        cout << f[i] << "    ";
    }

    cout << "\n\n\n";

    return 0;
}

Output:

We hope that this post helped you develop a better understanding of the concept of the application of a Pair Template and its implementation in C++. For any query, feel free to reach out to us via the comments section down below.

Keep Learning : )