[Solved] Design a way to sort the list of positive integers in the descending order according to frequency of the elements

Design a way to sort the list of positive integers in the descending order according to frequency of the elements. The elements with higher frequency come before those with lower frequency. Elements with the same frequency come in the same order as they appear in the given list.

Input

The first line of the input consists of an integer num, representing the number of elements in the list (N).

The second line consists of N space-separated integers representing the elements in the list.

Output

Print N space-separated integers representing the elements of the list sorted according to the frequency of elements present in the given list.

Example

Input:

19

1 2 2 3 3 3 4 4 5 5 5 5 6 6 6 7 8 9 10

Output:

5 5 5 5 3 3 3 6 6 6 2 2 4 4 1 7 8 9 10

Explanation:

The element 5 has highest frequency.

The elements 3 and 6 have same frequencies. So, their original order has been maintained in the output.

Similarly the frequecies of rest of elements will be  found and arranged.

So, the output will be: 5 5 5 5 3 3 3 6 6 6 2 2 4 4 1 7 8 9 10

Solution

import java.util.*;

public class a {

    public static int[] sort(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < arr.length; i++) {
            if (map.containsKey(arr[i])) {
                map.put(arr[i], map.get(arr[i]) + 1);
            } else {
                map.put(arr[i], 1);
            }
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        int[] res = new int[arr.length];
        int index = 0;
        for (Map.Entry<Integer, Integer> entry : list) {
            for (int i = 0; i < entry.getValue(); i++) {
                res[index++] = entry.getKey();
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        int[] res = sort(arr);
        for (int i = 0; i < res.length; i++) {
            System.out.print(res[i] + " ");
        }

    }
}

Happy Learning – If you require any further information, feel free to contact me.