http://www.practice.geeksforgeeks.org/problem-page.php?pid=493
Sorting Elements of an Array by Frequency
Given an array of integers, sort the array according to frequency of elements. For example, if the input array is {2, 3, 2, 4, 5, 12, 2, 3, 3, 3, 12}, then modify the array to {3, 3, 3, 3, 2, 2, 2, 12, 12, 4, 5}.
If frequencies of two elements are same, print them in increasing order.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output:
Print each sorted array in a seperate line. For each array its numbers should be seperated by space.
Constraints:
1 ≤ T ≤ 70
30 ≤ N ≤ 130
1 ≤ A [ i ] ≤ 60
Example:
Input:
1
5
5 5 4 6 4
Output:
4 4 5 5 6
import java.util.*;
import java.lang.*;
import java.io.*; class pair {
public int freq;
public int key;
public pair(int f, int k) {
super();
this.freq = f;
this.key = k;
}
} class cmp implements Comparator<pair> { public int compare(pair p1, pair p2) {
if(p1.freq != p2.freq) {
return p2.freq - p1.freq;
} else {
return p1.key - p2.key;
}
}
} class GFG { public static void pln(Object[] ls) {
for(int i=0; i<ls.length; ++i) {
System.out.print(ls[i]);
} System.out.println();
} public static void func(int[] arr) { int n = arr.length;
HashMap<Integer, Integer> mapping = new HashMap<Integer, Integer> (); for(int na: arr) {
if(!mapping.containsKey(na)) {
mapping.put(na, 0);
}
mapping.put(na, mapping.get(na) + 1);
} TreeSet<pair> freqToKey = new TreeSet<pair> (new cmp());
Iterator iter = mapping.entrySet().iterator();
while(iter.hasNext()) {
Map.Entry entry = (Map.Entry) iter.next();
int key = (int) entry.getKey();
int freq = (int) entry.getValue();
pair p = new pair(freq, key);
freqToKey.add(p);
} Object[] ls = freqToKey.toArray();
for(int i=0; i<ls.length; ++i) {
pair p = (pair) ls[i];
int freq = p.freq;
int key = p.key; while(freq > 0) {
--freq;
System.out.print(key + " ");
}
} System.out.println();
} public static void main (String[] args) {
Scanner in = new Scanner(System.in);
int times = in.nextInt(); while(times > 0) {
--times; int n = in.nextInt();
int[] arr = new int[n];
for(int i=0; i<n; ++i) {
arr[i] = in.nextInt();
} func(arr);
}
}
}