Write a java program to sort elements in descending order according to their frequency. If the two elements have same frequency then output them in the order of their input.
Example:
1 2 3 4 5 | Input: 1 2 2 4 3 Output: 2 2 1 4 3 Input: 1 2 2 3 3 3 4 5 6 6 Output: 3 3 3 2 2 6 6 1 4 5 |
Store the input into List and HaspMap. Sort the list according to the count stored in the HashMap. For this, we need to implement the comparator Interface.
Override the compare method, return 0 if the frequency (i.e count) of the two number is same otherwise return the frequency difference.
Recommended: Comparator Interface in Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | import java.util.*; public class SortByFrequency { public static void main(String args[]){ Scanner in = new Scanner(System.in); int n, num; System.out.println("Enter n"); n = in.nextInt(); HashMap<Integer, Integer> map = new HashMap<>(n); List<Integer> output = new ArrayList<>(n); System.out.println("Enter "+n+" Elements"); for(int i=0; i<n; i++){ num = in.nextInt(); int count = map.getOrDefault(num,0); map.put(num, count+1); //If the number is already present its count will be incremented output.add(num); //number is added to the list } Frequency frequency = new Frequency(map); //Pass the object as 2nd parameter which class implements the comparator Collections.sort(output,frequency); System.out.println("Sorted Result"); for(Integer x: output){ System.out.print(x+" "); } } } class Frequency implements Comparator<Integer>{ HashMap<Integer, Integer> map; Frequency(HashMap<Integer, Integer> map){ this.map = map; } @Override public int compare(Integer o1, Integer o2) { int f1 = map.get(o1), f2 = map.get(o2); if(f1 == f2) return 0; else return (f2 -f1); } } |
Output
1 2 3 4 5 6 | Enter n 10 Enter 10 Elements 1 2 2 3 3 3 4 5 6 6 Sorted Result 3 3 3 2 2 6 6 1 4 5 |