【算法】根据字符出现的频率进行排序

需求

输入一个字符串，对字符串的字符进行排列，按照其中字符的出现频率降序进行排序。

思路

可以定义一个字典，字典的key是字符，value是出现的次数，然后按照value进行排序。 大部分语言都可以对字典排序，但是go不支持，需要定义一个切片再排序重组。

实现

package chapter03

import (
	"sort"
	"strings"
)

type Pair struct {
	Key   string
	Value int
}

type PairList []Pair

func (p PairList) Len() int {
	return len(p)
}

func (p PairList) Less(i, j int) bool {
	return p[i].Value > p[j].Value
}

func (p PairList) Swap(i, j int) {
	p[i], p[j] = p[j], p[i]
}

func frequencySort(s string) string {
	if len(s) == 0 {
		return ""
	}

	var dict = make(map[string]int)
	for _, c := range s {
		dict[string(c)]++
	}

	var pairs = make(PairList, 0, len(dict))
	for k, v := range dict {
		pairs = append(pairs, Pair{k, v})
	}
	sort.Sort(pairs)
	var res string
	for _, p := range pairs {
		res += strings.Repeat(p.Key, p.Value)
	}
	return res
}