HackMD
451.Sort Characters By Frequency
tags: Medium,String,Hash Table,Sorting,Heap,Counting
451. Sort Characters By Frequency
題目描述
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
範例
Example 1:
Input: s = "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: s = "cccaaa"
Output: "aaaccc"
Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers.
Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "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.
Constraints:
- 1 <=
s.length<= 5 * 105 sconsists of uppercase and lowercase English letters and digits.
解答
Java
class Solution {
public String frequencySort(String s) {
// 1. Define HashMap
Map<Character, Integer> map = new HashMap<>();
// 2. Set character to HashMap
for(Character c : s.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1);
// 3. Bucket Sort
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<>();
bucket[frequency].add(key);
}
// 4. Append character to res from bucket
StringBuilder res = new StringBuilder();
for(int pos = bucket.length - 1; pos >= 0; pos--)
if(bucket[pos] != null)
for(char c : bucket[pos])
for(int i = 0; i < pos; i++)
res.append(c);
return res.toString();
}
}
Java 寫起來的痛苦指數好高QQ
Kobe Dec 3, 2022
Python
class Solution:
def frequencySort(self, s: str) -> str:
Q = dict()
for _s in s:
if _s in Q:
Q[_s] += 1
else:
Q[_s] = 1
stat = [ (k,v) for k,v in Q.items()]
stat = sorted(stat, key=lambda x: x[1], reverse=True)
result = ''
for _stat in stat:
result += _stat[0]*_stat[1]
return result
玉山 Dec 3, 2022
class Solution:
def frequencySort(self, s: str) -> str:
counter = Counter(s)
res = ""
for k, v in counter.most_common():
res += (k * v)
return res
寫完發現上面可以濃縮成一行
class Solution:
def frequencySort(self, s: str) -> str:
return "".join([k * v for k, v in Counter(s).most_common()])
Kobe Dec 3, 2022
C++
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> m;
for(char c:s)
{
if(m.find(c) == m.end())
m[c] = 1;
else
m[c]++;
}
vector<pair<char, int>> accu;
for(auto p : m)
accu.push_back({p.first, p.second});
sort(accu.begin(), accu.end(), [](pair<char, int> p1, pair<char, int>p2){
return p1.second > p2.second;
});
string res = "";
for(auto p : accu)
res+=string(p.second, p.first);
return res;
}
};
Time:
Extra Space:
XD Dec 3, 2022
Javascript
function frequencySort(s) {
const map = new Map();
for (let i = 0; i < s.length; i++) {
map.set(s[i], (map.get(s[i]) || 0) + 1);
}
const arr = Array.from(map).sort((a, b) => b[1] - a[1]);
let result = '';
for (const [key, value] of arr) {
result += key.repeat(value);
}
return result;
}
Marsgoat Dec 3, 2022
