Problem: You are given an array. You have to sort the array elements in decreasing order of their frequency.
eg. [2,3,4,2,8,1,1,2]
Output: [2 2 2 1 1 3 4 8]
Solution:
Method 1 (Use Sorting)
1) Use quick sort algorithm to sort the elements O(nlogn)
2) Scan the sorted array and construct a 2D array of element and count O(n).
3) Sort the 2D array according to count O(nlogn).
Input 2,3,4,2,8,1,1,2
After sorting we get
2 2 2 1 1 3 4 8
Now construct the 2D array as
2, 3
1, 2
3, 1
4, 1
8, 1
Sort by count
8, 3
2, 2
5, 2
6, 1
If we modify the input to 2 2 2 1 1 1 3 4 8, then we should get 2 2 2 1 1 1 3 4 8 and not 1 1 1 2 2 2 3 4 8.
To handle this, we should use indexes instead of the actual element, if two counts are same then we should first process(or print) the element with lower index.
Input 2 2 2 1 1 1 3 4 8
After sorting we get
Element 1 1 1 2 2 2 3 4 8
Index 3 4 5 1 2 3 6 7 8
Now construct the 2D array as
Index, Count
3, 3
1, 3
6, 1
7, 1
8, 1
Sort by count (consider indexes in case of tie)
Index, Count
3, 3
1, 3
6, 1
7, 1
8, 1
Print the elements using indexes in the above 2D array.
2 2 2 1 1 1 3 4 8
Method 2 (Use Hash)
Using a hashing mechanism, we can store the elements (also first index) and their counts in a hash. Finally, sort the hash elements according to their counts.
If you have any better approach, Please write or comment below.
after sorting the array how would you get to know which value corresponds to which element of original array…i mean our array is :2,3,4,2,8,1,1,2 after applying operations we get array as 0,2,3,1,0,0,0,1
now if we sort the array how we would able to map which value corresponds to which element?
To solve this problem. we will not sort the last array, we simply start printing value of the array from minimum frequency value 1 to maximum frequency value
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
public class FrequencySorter
{
private static int[] a;
public static void print()
{
for (int i : a)
{
System.out.print(i + ” “);
}
}
public static int[] sort()
{
Arrays.sort(a);
Map m = new TreeMap();
int counter = 0;
int index = 0;
int previous = a[index];
for (int i : a)
{
if (i == previous)
{
counter++;
}
else
{
m.put(counter, previous);
counter = 0;
}
previous = i;
}
int[] b = new int[m.size()];
int n = m.size()-1;
for (Integer i : m.values())
{
b[n] = i;
n–;
}
return b;
}
public static void main(String[] args)
{
int[] b = {1,2,2,1,3,3,3,3,3,4,5};
a = b;
int[] s = sort();
print();
System.out.println();
for (int i : s)
{
System.out.print(i + ” “);
}
}
}
I could do that in O(N) with O(N) space. Basically, what I did were:
1. Put key and its frequency (as value) in a hash map
2. Put all of the entries in a tree map which a custom Comparator. In this comparator, we first compare frequency and also the key to determine the order in the tree map.
3. Iterator through the Tree map and build the output ( or you can put it back to an array output)
Below is the code in java:
public static void printOutFrequencySort(int[] a) {
//Print input.
for( int i = 0; i < a.length; ++i) {
System.out.print( a[i] + " ");
}
System.out.println();
Map counting = new HashMap();
Comparator cp = new KeyValueComparator(counting);
TreeMap treeMap = new TreeMap(cp);
for( int i = 0; i < a.length; ++i) {
Integer value = counting.get(a[i]);
if( value == null) {
counting.put(a[i], new Integer(1));
} else {
counting.put( a[i], new Integer(value + 1));
}
}
System.out.println( counting);
treeMap.putAll(counting);
System.out.println( treeMap );
// print output
for( Map.Entry entry : treeMap.entrySet()) {
Integer value = entry.getKey();
Integer frequency = entry.getValue();
for( int i = 0; i < frequency.intValue(); ++i) {
System.out.print(value + " ");
}
}
System.out.println();
}
static class KeyValueComparator implements Comparator {
Map map;
KeyValueComparator(Map map) {
this.map = map;
}
@Override
public int compare(Integer k1, Integer k2) {
Integer v1 = map.get(k1);
Integer v2 = map.get(k2);
if( v1 > v2) {
return -1;
} else if ( v1 == v2) {
return k1 < k2 ? -1 : 1;
}
return 1;
}
}
//get the element count
//sort the map according to key Values
//print the elements
public class SortElementsByFrequency
{
static LinkedHashMap hm = new LinkedHashMap();
public static void main(String[] args)
{
//int[] a = {2,3,4,2,8,1,1,2};
int[] a = {2,2,2,1,1,1,3,4,8};
frequencyCount(a);
//Adding entrySet to LinkedList
List<Map.Entry> list = new LinkedList<Map.Entry>(hm.entrySet());
Collections.sort(list,new Comparator<Map.Entry>()
{
@Override
public int compare(Entry arg0,
Entry arg1) {
return arg1.getValue()-arg0.getValue();
}
});
for(Map.Entry i:list)
{
for(int j=0;j<i.getValue();j++)
{
System.out.print(i.getKey()+" ");
}
System.out.println();
}
}
public static void frequencyCount(int[] a)
{
for(int i=0;i<a.length;i++)
{
if(hm.containsKey(a[i]))
hm.put(a[i],hm.get(a[i])+1);
else
hm.put(a[i], 1);
}
}
}
determine the frequency of each element in an array of sorted elements
example: input: 1,1,4,4,5,6,7,7,7
output: 1–2
4–2
5–1
6–1
7–3
note: take an array of integer as user input and write the generic logic