Sort
the elements of an array by number of times they repeated in
ascending order.
For
Example
let
array 'a' has 5, 4, 3, 2, 1, 0, 5, 3, 2, 4, 1, 2, 3, 5
Then
the output should be like below.
0
1 1 4 4 2 2 2 3 3 3 5 5 5
Procedure:
Step
1: Find frequency count of each element in the array and
construct map.
For
the above example
Value | Frequency |
0 | 1 |
1 | 2 |
2 | 3 |
3 | 3 |
4 | 2 |
5 | 3 |
Step
2: You got the frequency for each element in the array, now apply
sorting logic based on the frequency.
import java.util.*; public class SortByFrequency { static void sortByFreq(int a[]){ Map<Integer, Integer> map = new TreeMap<> (); /* Logic to place the elements to Map */ for(int i=0; i<a.length; i++){ if(map.get(a[i]) == null){ map.put(a[i], 1); } else{ int frequency = map.get(a[i]); map.put(a[i], frequency+1); } } //System.out.println(map); List list = new LinkedList(map.entrySet()); /* Sort the list elements based on frequency */ Collections.sort(list, new Comparator() { @Override public int compare(Object obj1, Object obj2) { return ((Comparable) ((Map.Entry) (obj1)).getValue()) .compareTo(((Map.Entry) (obj2)).getValue()); } }); int count=0; /* Place the elements in to the array based on frequency */ for (Iterator it = list.iterator(); it.hasNext();) { Map.Entry entry = (Map.Entry) it.next(); int key = (int)entry.getKey(); int val = (int)entry.getValue(); for(int i=0; i < val; i++){ a[count] = key; count++; } } } public static void main(String args[]){ int a[] = {5,4,3,2,1,0,5,3,2,4,1,2,3,5}; System.out.println("Before Sorting"); for(int i=0; i<a.length; i++){ System.out.print(a[i] +" "); } sortByFreq(a); System.out.println("\nAfter Sorting"); for(int i=0; i<a.length; i++){ System.out.print(a[i] +" "); } } }
Output
Before Sorting 5 4 3 2 1 0 5 3 2 4 1 2 3 5 After Sorting 0 1 1 4 4 2 2 2 3 3 3 5 5
No comments:
Post a Comment