0451. 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.

``````

## 代码 #

``````
package leetcode

import (
"sort"
)

func frequencySort(s string) string {
if s == "" {
return ""
}
sMap := map[byte]int{}
cMap := map[int][]byte{}
sb := []byte(s)
for _, b := range sb {
sMap[b]++
}
for key, value := range sMap {
cMap[value] = append(cMap[value], key)
}

var keys []int
for k := range cMap {
keys = append(keys, k)
}
sort.Sort(sort.Reverse(sort.IntSlice(keys)))
res := make([]byte, 0)
for _, k := range keys {
for i := 0; i < len(cMap[k]); i++ {
for j := 0; j < k; j++ {
res = append(res, cMap[k][i])
}
}
}
return string(res)
}

``````