451. Sort Characters By Frequency

451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:"tree"Output:"eert"Explanation:'e' appears twice while 'r' and 't' both appear once.So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:"cccaaa"Output:"cccaaa"Explanation:Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:"Aabb"Output:"bbAa"Explanation:"bbaA" is also a valid answer, but "Aabb" is incorrect.Note that 'A' and 'a' are treated as two different characters.

思路： hashmap求frequency加排序，排序可以用bucket sort or heap sort。

class Solution { public String frequencySort(String s) { Map map = new HashMap(); int max = 0; for(char c : s.toCharArray()) { map.put(c, map.getOrDefault(c, 0) + 1); max = Math.max(map.get(c), max); } List[] bucket = new List[max + 1]; int count = 0; for(char c : map.keySet()) { int index = map.get(c); if(bucket[index] == null) bucket[index] = new ArrayList(); bucket[index].add(c); count++; } StringBuilder sb = new StringBuilder(); sb.append(""); for(int i = bucket.length-1; i >= 0; i--) { if(bucket[i] != null) { for(char c : bucket[i]) { for(int j = 0; j < i; j++) sb.append(c); count--; } if(count == 0) break; } } return sb.toString(); }}

/** * @param {string} s * @return {string} */var frequencySort = function(s) { const len = s.length if (!len) { return s } const map = new Map() const temp = [] let str = '' for (let i = 0; i < len; i++) { const char = s[i] if (!map.has(char)) { map.set(char, 1) } else { map.set(char, map.get(char) + 1) } } map.forEach((val, key) => { temp.push({ val, key }) }) temp.sort((a, b) => b.val - a.val) temp.forEach(item => { str += item.key.repeat(item.val) }) return str};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。