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
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 |