451. Sort Characters By Frequency

• bucket sort

  	class Solution {
  	public String frequencySort(String s) {
  	Map<Character, Integer> map = new HashMap<>();
  	for (char c : s.toCharArray()) {
  	if (map.containsKey(c)) {
  	map.put(c, map.get(c) + 1);
  	} else {
  	map.put(c, 1);
  	}
  	}
  	// concrete style
  	// PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
  	// (a, b) -> b.getValue() - a.getValue()
  	// );
  	PriorityQueue<Map.Entry<Character, Integer>> pq = new PriorityQueue<>(
  	new Comparator<Map.Entry<Character, Integer>>() {
  	@Override
  	public int compare(Map.Entry<Character, Integer> a, Map.Entry<Character, Integer> b) {
  	return b.getValue() - a.getValue();
  	}
  	}
  	);
  	pq.addAll(map.entrySet());
  	StringBuilder sb = new StringBuilder();
  	while (!pq.isEmpty()) {
  	Map.Entry e = pq.poll();
  	for (int i = 0; i < (int) e.getValue(); i++) {
  	sb.append(e.getKey());
  	}
  	}
  	return sb.toString();
  	}
  	}
  	class Solution {
  	// O(n) O(n)
  	public String frequencySort(String s) {
  	Map<Character, Integer> map = new HashMap<>();
  	for (char c : s.toCharArray()) {
  	if (map.containsKey(c)) {
  	map.put(c, map.get(c) + 1);
  	} else {
  	map.put(c, 1);
  	}
  	}
  	List<Character>[] bucket = new List[s.length() + 1];
  	for (char c : map.keySet()) {
  	int count = map.get(c);
  	if (bucket[count] == null) {
  	bucket[count] = new ArrayList<Character>();
  	}
  	bucket[count].add(c);
  	}
  	StringBuilder sb = new StringBuilder();
  	for (int i = s.length(); i > 0; i--) {
  	if (bucket[i] != null) {
  	for (char c : bucket[i]) {
  	for (int j = 0; j < i; j++) {
  	sb.append(c);
  	}
  	}
  	}
  	}
  	return sb.toString();
  	}
  	}

  view raw 451_0927.java hosted with ❤ by GitHub