Sort elements by frequency

help
,
1

Let array A [] be composed of n integers. Your task is to sort the array by the number of occurrences of array elements. The number appears many times first. If two elements have the same number of occurrences, the smaller number comes first. For example A [] = {5, 5, 4, 6, 4}, we get the result A [] = {4, 4, 5, 5, 6}.
image
I need a good idea to do this, thank you everyone.

2

array to undordered_map for counting frequency
then map to array of pairs(value, frequency) and sort it using comparator function.

EDIT: Here’s the code
IDK if its the best approach or not but it works

2 Likes
3

You can use pair concept and make an array of pairs which has one value as an element and another value as its occurrence count like for array {1,2,1,4} the occurrence array would be {{1(elements),2(its occurrence count)},{2,1},{4,1}} and then use Quicksort. Thus the time complexity may fall to O(NlogN); as with map insertion operation is has log time complexity, so for an array with a large number of elements, it might give Time limit exceed, but it’s very unlikely. Otherwise, sunny’s solution approach is also right and would get accepted across all platforms, but if you face any time-related issue, try this approach.

1 Like
4

@shubsanskar
1.Value of array isn’t upto n, keeping count using simply only pair is not feasible.(If I misunderstood what you said,then please elaborate how will you keep count in O(n) time?)
2.Insertion in unordered map has amortised constant insertion time.

1 Like
5

Hey, @sunny_52525 i do not disagree with your answer just giving the answer for the same type of question which has bounded inputs, so what I am suggesting that first make a temporary array of limited range, then traverse the given array and increase the index value by one with each occurrence in the temporary array, then make a pair array with the element and its index then sort it using quicksort. Just a solution to a variant of this question.

2 Likes
6

I have not learned how to write this, can you clarify what it is: for(auto x: a)

7

Simply iterating all values in a
It is like
for(i=0;i<n;i++)
{
x=a[i];
…}

1 Like
8

Bro do not post your homework here , u r not giving any link as u yesterday said that this is from my assignment before asking plzz google :slight_smile:

1 Like
9

for each loop

10

I thank you very much

11

I’m sorry I don’t have the link to give to you, and this is the solution for yesterday, I am still very grateful for your contribution to me: ZXpwRl - Online C++ Compiler & Debugging Tool - Ideone.com