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.

Submissions

• golang

import (
    "sort"
    "strings"
)
func frequencySort(s string) string {
    save := make(map[rune]int)
    for _,v := range s{
        if _,ok := save[v]; ok{
            save[v] ++
        }else{
            save[v] = 1
        }
    }

    type kv struct {
        Key   rune
        Value int
    }

    var ss []kv
    for k, v := range save {
        ss = append(ss, kv{k, v})
    }

    sort.Slice(ss, func(i, j int) bool {
        return ss[i].Value > ss[j].Value  // 降序
    })

    var res string
    for _, kv := range ss {
        res += strings.Repeat(string(kv.Key),kv.Value)
    }
    return res
}

• scala

代码是对的，但是超时了，需要讨论下高阶函数是不是耗时的问题

object Solution {
    def frequencySort(s: String): String = {
        if (s == "")
            return ""
        return s.toCharArray.groupBy(identity).mapValues(_.length).toList.sortBy(-_._2).map(i => i._1.toString * i._2).reduce(_+_)
    }
}