Last Updated: 24 Mar, 2021
Sort Elements By Frequency
Easy
Asked in companies
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.
For Example :
Input: arr[] = {2, 5, 2, 8, 5, 6, 8, 8}
Output: arr[] = {8, 8, 8, 2, 2, 5, 5, 6}
Explanation :
When you sort the array based on the decreasing order of the frequency of repetition of integers in the original array,
you’ll find that the element ‘8’ is the integer with the most repeated values therefore it would be arranged first after which since both 2 and 5 have the same number of repeated
values in the original array but since the 2 arrived first so we will first arrange 2 and then 5 in our resultant array, while would be the last element after sorting here.
Input Format :
The first line of input contains a single integer ‘T’ denoting the number of test cases that would be there.
The first line of each test case contains a single integer ‘N’ denoting the number of integers that would be given.
And the next line contains ‘N’ space-separated integers which are the elements of the list.
Output Format :
For each test case, print the sorted list of elements by the decreasing order of their frequency of repetition in the list.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 3000
1 <= NUMS[i] <= 10^6
Where 'NUMS[i]' denotes the 'ith' element of the given array.
Time Limit: 1sec
Approaches
The idea here is to keep a maintained list of the counts of the various elements given in the list and sort it in descending order based on their frequency counts and now keep the index values of the items and order them in ascending order.
The algorithm will be-
- The idea is to write a custom comparison method to solve this problem. Let the two elements to be compared are ‘x’ and ‘y’. Then.
- If ‘x’ and ‘y’ have different frequencies, then the one with more frequency should be treated as smaller than the other.
- If ‘x’ and ‘y’ have the same frequencies, then the one with less index should be treated as smaller than the other.
- For each array element, insert into the dictionary its frequency and index of its first occurrence in the array.
- Sort the values based on a custom comparator and finally return the sorted list having arranged items.
Similar problems