Sort Elements by frequency. For this problem I m not getting the required output. How can I solve this

Question

Problem Statement

You are given a list of a repeated set of integers. Your task for the problem is to return a list of the given elements in decreasing sorted order of their frequency of repetition in the given list with the element with the highest frequency of repetition first and so on. Note: If two numbers have the same frequency then keep the one that was present before the other in the original given list (array) first.

INPUT: 
1 3 2 2 2 3 4 3 1
OUTPUT:
3 3 3 2 2 2 1 1 4

Code:

#include <bits/stdc++.h> 
using namespace std;

vector<int> sortByFrequency(vector<int>& nums){
    unordered_map <int,int> mpp;
    vector <int> temp;
    for(int i=0;i<nums.size();i++)
    {
        mpp[nums[i]]++;
    }

    int max_ele;
    int max = INT_MIN;

    while(mpp.empty()==0)
    {
        for(auto it : mpp)
        {
          if (it.second > max) {
            max = it.second;
            max_ele = it.first;
          }
        }
        while(max--)
        {
            temp.push_back(max_ele);
        }
        
        mpp.erase(max_ele);
    }

    return temp;
}

int main()
{
    vector <int> arr = {1, 3, 2, 2, 2, 3, 4, 3, 1};
    vector <int> res;
    res = sortByFrequency(arr);

    for(auto it: res)
    {
        cout << it << " ";
    }
}

This code gives the output of:

2 2 2 3 3 3 1 1 4

But Actual output should be:

3 3 3 2 2 2 1 1 4

That is it violates this condition If two numbers have the same frequency then keep the one that was present before the other in the original given list (array) first.

How can I solve this?

The most efficient way to deal with this might depend on the size of the original list, the number of distinct values in the list, and the range of the values in the list. You didn't provide any information about these things. — Simon Goater
– Simon Goater, Commented Jul 23, 2023 at 9:50
Where did you learn #include <bits/stdc++.h>? Wherever that was, block that site in your browser, never go there again, and learn C++ from a good book. — Eljay
– Eljay, Commented Jul 23, 2023 at 12:33
@273K After finding the element with maximum frequency. Delete that Key,Value pair from the unordered map. mpp.empty()==0 will check if the map is empty only if it is not empty we will find the element with maximum frequency — vss_suba
– vss_suba, Commented Jul 23, 2023 at 12:43
I did not ask what this code did, I asked why did you compare the bool value with the number 0. — 3CEZVQ
– 3CEZVQ, Commented Jul 23, 2023 at 16:15

3CEZVQ · Accepted Answer · 2023-07-22 19:54:10Z

0

Your O(N^2) solution is not optimal and, as you know it, is wrong.

Here what I made for you for O(N*log(N)) taking into account the topics Why is "using namespace std;" considered bad practice? and Why should I not #include <bits/stdc++.h>?

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

std::vector<int> sortByFrequency(std::vector<int>& nums) {
  std::unordered_map<int, int> mpp;
  for (const auto num : nums)
    mpp[num]++;

  // Sort |num| by the frequency of occurrence of the elements.
  // Different elements with same frequencies are considered equal elements.
  std::stable_sort(nums.begin(), nums.end(),
                   [&mpp](int l, int r) { return mpp[l] > mpp[r]; });

  // Merge equal elements.
  std::vector<int> ret;
  for (const auto num : nums) {
    if (mpp.count(num)) {
      ret.insert(ret.end(), mpp[num], num);
      mpp.erase(num);
    }
  }

  return ret;
}

int main() {
  std::vector<int> nums = {1, 3, 2, 2, 2, 3, 4, 3, 1};
  auto res = sortByFrequency(nums);

  for (auto num : res)
    std::cout << num << " ";
}

Output

3 3 3 2 2 2 1 1 4

answered Jul 22, 2023 at 19:54

3CEZVQ

42.9k11 gold badges91 silver badges100 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

vss_suba Over a year ago

Can you explain me this portion of code @273K

std::stable_sort(nums.begin(), nums.end(),                    [&mpp](int l, int r) { return mpp[l] > mpp[r]; });    // Merge equal elements.   std::vector<int> ret;   for (const auto num : nums) {     if (mpp.count(num)) {       ret.insert(ret.end(), mpp[num], num);       mpp.erase(num);     }   }

Collectives™ on Stack Overflow

Sort Elements by frequency. For this problem I m not getting the required output. How can I solve this

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related