451. Sort Characters By Frequency (类比347priorityqueue)

[Shawngbk]

keySet是键的集合，Set里面的类型即key的类型 entrySet是 键-值 对的集合，Set里面的类型是Map.Entry keySet()的速度比entrySet()慢了很多 使用entrySet则必须将map对象转换为Map.Entry，keySet则不需要

import java.util.Map.Entry; public class Solution { public String frequencySort(String s) { Map<Character, Integer> map = new HashMap<>(); for(int i = 0; i < s.length(); i++) { char key = s.charAt(i); if(!map.containsKey(key)) { map.put(key, 1); } else { int val = map.get(key); map.put(key, val+1); } }

    List<Entry<Character, Integer>> list = new ArrayList<>(map.entrySet());
    Collections.sort(list, new Comparator<Entry<Character, Integer>>() {
        public int compare(Entry<Character, Integer> o1, Entry<Character, Integer> o2) {
            //if you want to make increasing order just need to 
            // return o1.getValue().compareTo(o2.getValue());
            return o2.getValue().compareTo(o1.getValue());
        }
    });

    StringBuilder res = new StringBuilder();
    for(Entry<Character, Integer> pair : list) {
        int num = pair.getValue();
        char c = pair.getKey();
        for(int i = 0; i < num; i++) {
            res.append(c);
        }
    }

    return res.toString();
}

}

---

class Entry { char c; int f;

public Entry(char ch, int frequency) {
    c = ch;
    f = frequency;
}

}

class myCompare implements Comparator { public int compare(Entry e1, Entry e2) { return e2.f - e1.f; } }

public String frequencySort(String s) { PriorityQueue queue = new PriorityQueue(new myCompare()); Map<Character, Entry> map = new HashMap<Character, Entry>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); Entry e; if (!map.containsKey(c)) { e = new Entry(c, 1); map.put(c, e); } else { e = map.get(c); e.f++; queue.remove(e); } queue.add(e); } StringBuilder res = new StringBuilder(); while (!queue.isEmpty()) { Entry e = queue.poll(); for (int i = 0; i < e.f; i++) { res.append(e.c); } } return res.toString(); }

[Shawngbk]

Amazon Google