BiruLyu
6/5/2017 - 6:50 PM

## 451. Sort Characters By Frequency(Bucket).java

``````public class Solution {
private class Node {
char ch;
int count;
public Node(char ch, int cnt) {
this.ch = ch;
this.count = cnt;
}
}
public String frequencySort(String s) {
if(s == null || s.length() < 3) return s;
char[] ch = s.toCharArray();
Queue<Node> maxHeap = new PriorityQueue<Node>( new Comparator<Node>() {
public int compare (Node n1, Node n2) {
return n2.count - n1.count;
}
});
Arrays.sort(ch);
int count = 1;
for(int i = 1; i < ch.length; i++) {
if(ch[i] == ch[i - 1]) {
count++;
continue;
}
maxHeap.offer(new Node(ch[i - 1], count));
count = 1;
}
maxHeap.offer(new Node(ch[ch.length - 1], count));

StringBuilder temp = new StringBuilder();
while(!maxHeap.isEmpty()) {
Node cur = maxHeap.poll();
int cnt = cur.count;
char tempChar = cur.ch;
while(cnt != 0) {
temp.append(tempChar);
cnt--;
}
}
return temp.toString();
}
}``````
``````public class Solution {
public String frequencySort(String s) {
int[] freq = new int [256];
for (char ch: s.toCharArray()) freq[ch]++;
TreeMap<Integer, List<Character>> tree = new TreeMap<Integer, List<Character>>();
for (int i=0; i<freq.length; i++) {
if (freq[i] > 0) {
if (!tree.containsKey(freq[i])) {
}
}
}
StringBuilder sb = new StringBuilder();
while(tree.size() > 0) {
Map.Entry<Integer, List<Character>> entry = tree.pollLastEntry();
for (Character ch: entry.getValue()) {
sb.append(new String(new char[entry.getKey()]).replace('\0', ch));
}
}
return sb.toString();

}
}``````
``````public 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);
}
}
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();
}
}
);
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();
}
}``````
``````public 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);
}
}
List<Character> [] bucket = new List[s.length() + 1];
for (char key : map.keySet()) {
int frequency = map.get(key);
if (bucket[frequency] == null) {
bucket[frequency] = new ArrayList<>();
}
}
StringBuilder sb = new StringBuilder();
for (int pos = bucket.length - 1; pos >=0; pos--) {
if (bucket[pos] != null) {
for (char num : bucket[pos]) {
for (int i = 0; i < map.get(num); i++) {
sb.append(num);
}
}
}
}
return sb.toString();
}
}
``````