我正在尝试构建最大字符堆。首先按频率排序,如果频率相同,则按字母顺序排序。
Map<Character, Integer> map = new HashMap<>();
for(int i = 0; i < n; i++) {
char c = s.charAt(i);
map.put(c, map.getOrDefault(c, 0) + 1);
}
Queue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
@Override
public int compare(Character c1, Character c2){
if(map.get(c1) == map.get(c2)){
return c1 < c2 ? -1 : (c1 == c2 ? 0 : 1);
//return (char)c1 - (char)c2; same output
}
return map.get(c2) - map.get(c1);
}
});
for(char key : map.keySet()){
pq.offer(key);
System.out.println(key + " has freq " + map.get(key));
}
while(!pq.isEmpty()) {
System.out.print(pq.poll() + " ");
}
我将26个字母放入这个maxheap中,每个字母的频率相同5000。
但输出顺序是 'a', 'z', 'y', 'x'......, 'c', 'b'。
我不明白为什么频率5000的输出是这样的。我怎样才能得到正确的订单?
最佳答案
鉴于所有频率都相同,您的 if 语句是错误的。您可以使用内置方法来比较对象并返回结果
Integer f1 = map.get(c1);
Integer f2 = map.get(c2);
int x = f1.compareTo(f2)
if(x == 0){
return Character.compare(c1, c2);
}
return x;
关于Java,如何在比较器中按字母顺序对字符进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58072204/