451 Sort Characters By Frequency-白红宇

先统计次数，再按次数构造新的string。思路没什么难，写起来还有点麻烦。用了priorityqueue。。

class Wrapper {		public char c;		public int freq;		public Wrapper(char c, int freq) {			this.c = c;			this.freq = freq;		}	}	public String frequencySort(String s) {		if (s==null || s.length() == 0) return "";		Map
    
      map = new HashMap<>();		Set
     
       set = new HashSet<>();		for (int i = 0; i < s.length(); i++) {			int count = map.getOrDefault(s.charAt(i), 0);			map.put(s.charAt(i), ++count);			set.add(s.charAt(i));		}		PriorityQueue
      
        pq = new PriorityQueue<>(new Comparator
       
        () {			@Override			public int compare(Wrapper o1, Wrapper o2) {				return o1.freq - o2.freq;			}		});		for (char c : set) {			pq.offer(new Wrapper(c, map.get(c)));		}		StringBuilder sb = new StringBuilder();		while (!pq.isEmpty()) {			Wrapper w = pq.poll();			for (int i = 0; i < w.freq; i++) {				sb.insert(0, w.c);			}		}		return sb.toString();	}复制代码

因为用了PriorityQueue所以复杂度是O(nlogn)。看了别人的答案，有个是O(n)的，用了数组的index表示出现的次数。而且，我上面用了hashset，因为我不太会hashmap的遍历，下面的代码也展示了hashmap的遍历方法, for(char c : map.keySet())：

public String frequencySort(String s) {    if (s == null) {        return null;    }    Map
    
      map = new HashMap();    char[] charArray = s.toCharArray();    int max = 0;    for (Character c : charArray) {        if (!map.containsKey(c)) {            map.put(c, 0);        }        map.put(c, map.get(c) + 1);        max = Math.max(max, map.get(c));    }    List
     
      [] array = buildArray(map, max);    return buildString(array);}private List
      
       [] buildArray(Map
       
         map, int maxCount) {    List
        
         [] array = new List[maxCount + 1];    for (Character c : map.keySet()) {        int count = map.get(c);        if (array[count] == null) {            array[count] = new ArrayList();        }        array[count].add(c);    }    return array;}private String buildString(List
         
          [] array) { StringBuilder sb = new StringBuilder(); for (int i = array.length - 1; i > 0; i--) { List
          
            list = array[i]; if (list != null) { for (Character c : list) { for (int j = 0; j < i; j++) { sb.append(c); } } } } return sb.toString();}复制代码