class Solution {
public:
string frequencySort(string s) {
}
};
451. 根据字符出现频率排序
给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
示例 1:
输入: s = "tree" 输出: "eert" 解释: 'e'出现两次，'r'和't'都只出现一次。 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
示例 2:
输入: s = "cccaaa" 输出: "cccaaa" 解释: 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例 3:
输入: s = "Aabb" 输出: "bbAa" 解释: 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。 注意'A'和'a'被认为是两种不同的字符。
提示:
1 <= s.length <= 5 * 105s 由大小写英文字母和数字组成原站题解
golang 解法, 执行用时: 12 ms, 内存消耗: 4.5 MB, 提交时间: 2022-11-17 17:48:34
func frequencySort(s string) string {
cnt := map[byte]int{}
maxFreq := 0
for i := range s {
cnt[s[i]]++
maxFreq = max(maxFreq, cnt[s[i]])
}
buckets := make([][]byte, maxFreq+1)
for ch, c := range cnt {
buckets[c] = append(buckets[c], ch)
}
ans := make([]byte, 0, len(s))
for i := maxFreq; i > 0; i-- {
for _, ch := range buckets[i] {
ans = append(ans, bytes.Repeat([]byte{ch}, i)...)
}
}
return string(ans)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
golang 解法, 执行用时: 0 ms, 内存消耗: 4.7 MB, 提交时间: 2022-11-17 17:47:49
func frequencySort(s string) string {
cnt := map[byte]int{}
for i := range s {
cnt[s[i]]++
}
type pair struct {
ch byte
cnt int
}
pairs := make([]pair, 0, len(cnt))
for k, v := range cnt {
pairs = append(pairs, pair{k, v})
}
sort.Slice(pairs, func(i, j int) bool { return pairs[i].cnt > pairs[j].cnt })
ans := make([]byte, 0, len(s))
for _, p := range pairs {
ans = append(ans, bytes.Repeat([]byte{p.ch}, p.cnt)...)
}
return string(ans)
}
python3 解法, 执行用时: 44 ms, 内存消耗: 15.8 MB, 提交时间: 2022-11-17 17:44:26
class Solution:
def frequencySort(self, s: str) -> str:
c = Counter(s)
return ''.join(sorted([k * v for k, v in c.items()], key=lambda x: -len(x)))