→ wwndbk: 大師 12/03 13:09
推 v03516020: 大師 12/03 13:09
※ 編輯: Rushia (122.100.75.86 臺灣), 12/03/2022 13:11:31
451. Sort Characters By Frequency
給你一個字串s，我們要把他的所有字元依照「每個字元的出現頻率」降序排列。
Example：
Input: s = "tree"
Output: "eert"
Explanation: 'e'出現兩次所以排最前面，'r'和't'出現一次哪個在前面都OK。
思路：
1.用一個Map統計每個字元的出現頻率
2.用一個Heap根據map裡的頻率來排序
3.把heap裡面的元素拿出來append指定次數。
Java Code：
---------------------------------------
class Solution {
public String frequencySort(String s) {
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
Queue<Character> queue = new PriorityQueue<>(
(o1, o2) -> map.get(o2).compareTo(map.get(o1))
);
for (Map.Entry<Character, Integer> kv : map.entrySet()) {
queue.offer(kv.getKey());
}
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
char c = queue.poll();
for (int i = 0; i < map.get(c); i++) {
sb.append(c);
}
}
return sb.toString();
}
}
---------------------------------------
--
https://i.imgur.com/3e5CZfj.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.75.86 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1670044080.A.C13.html