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, Jul 23 '23 at 09:50
Where did you learn `#include `? Wherever that was, block that site in your browser, never go there again, and learn C++ from a good book. — Eljay, Jul 23 '23 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, Jul 23 '23 at 12:43
I did not ask what this code did, I asked why did you compare the bool value with the number 0. — 273K, Jul 23 '23 at 16:15

score 0 · Answer 1 · answered Jul 22 '23 at 19:54

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

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 ret; for (const auto num : nums) { if (mpp.count(num)) { ret.insert(ret.end(), mpp[num], num); mpp.erase(num); } }` — vss_suba, Jul 23 '23 at 12:48

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

1 Answers1