Based on the DescendPrint link, this one improved by directly sorting the HashMap.Entry in ArrayList.
package weeklychallenge1;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;
import java.util.Map.Entry;
/*
* Given a string, sort its chars by their number of
* appearance in descending order. e.g. input: abcbaa, output: aaabbc.
*/
public class DescendPrint {
/*
* Step1, put all in hashMap. This costs O(n) time, O(n) space
* Step2, initial List. Put Entry to this list. Step3,
* sort the list according to value. This costs O(nlogn) time, it doesn’t
* cost extra space. Step3, print result from hashTree Total time, O(n +
* nlogn) = O(nlogn) Total space, O(n)
*/
public static void descendPrint2(String str) {
if (str == null || str.length() == 0) {
return;
}
// put char count to hashMap
Map hm = new HashMap();
for (int i = 0; i < str.length(); i++) {
if (!hm.containsKey(str.charAt(i))) {
hm.put(str.charAt(i), 1);
continue;
}
int count = hm.get(str.charAt(i));
hm.put(str.charAt(i), ++count);
}
// Sort hashMap according to value.
Set < Entry < Character, Integer > > set = hm.entrySet();
ArrayList < Entry < Character, Integer > > list = new ArrayList < Entry < Character, Integer > > ( set);
Collections.sort(list, new DescendComparator());
// Print result
for (Entry entry : list) {
char ch = entry.getKey();
int count = entry.getValue();
for (int i = 0; i < count; i++) {
System.out.print(ch);
}
}
}
public static void main(String[] args) {
String str = “abcccbbaaa”;
descendPrint2(str);
}
}
class DescendComparator implements Comparator> {
public int compare(Entry entry1,
Entry entry2) {
int count1 = entry1.getValue();
int count2 = entry2.getValue();
return count2 – count1;
}
}