Решение задачи 451 “Sort Characters By Frequency” с LeetCode.
Условие задачи
Дана строка, необходимо отсортировать в ней буквы по убыванию количества вхождений этих букв.
пример
1
2
3
4
5
6
7
8
9
|
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.
|
1
2
3
4
5
6
7
8
9
|
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.
|
1
2
3
4
5
6
7
8
9
|
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.
|
Решение
Map + Bucket sort
Идея алгоритма:
Создать мапу буква <-> количество вхождений.
Пройтись по строке и посчитать кол-во вхождений.
Создать массив (черпак), где индекс массива – количество вхождений, а значений – буквы встреающиеся столько раз. Записать сюда данные из мапы.
Пройтись по массиву в порядке убывания индексов, если подмассива по индексу размеров больше нуля ( то есть какие-то буквы встретились в исходной строке столько раз – сколько значение индекса). И добавить к результирующей строка в конец столько раз каждой буквы, сколько значение индекса.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
func frequencySort(s string) string {
a := make(map[byte]int, 0 )
maxc:=0
for idx:=range s {
a[s[idx]]++
if a[s[idx]]>maxc {
maxc = a[s[idx]]
}
}
bucket := make([][]byte, maxc+1)
for idx:=range a {
if bucket[a[idx]] == nil {
bucket[a[idx]] = make([]byte,0)
}
bucket[a[idx]] = append(bucket[a[idx]], idx)
}
res := ""
for idx:=maxc;idx>=0;idx-- {
if len(bucket[idx])!=0 {
for kdx:=range bucket[idx] {
for jdx:=0;jdx<idx;jdx++ {
res+=string(bucket[idx][kdx])
}
}
}
}
return res
}
|
Priority queue
Идея:
Создать очередь с приоритетом, где приоритет - кол-во вхождений. А значение элемента - буква.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
|
func frequencySort(s string) string {
q := make(map[byte]int, 0)
for idx:=range s {
q[s[idx]]++
}
pq := make(PQ, len(q))
i := 0
for value, priority := range q {
pq[i] = &Item{
value: value,
priority: priority,
index: i,
}
i++
}
heap.Init(&pq)
res := ""
for pq.Len() > 0 {
item := heap.Pop(&pq).(*Item)
for idx:=0;idx<item.priority;idx++{
res+=string(item.value)
}
}
return res
}
type Item struct {
value byte
priority int
index int
}
type PQ []*Item
func (pq PQ) Len() int {
return len(pq)
}
func (pq PQ) Less(i, j int) bool {
return pq[i].priority > pq[j].priority
}
func (pq PQ) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
pq[i].index = i
pq[j].index = j
}
func (pq *PQ) Push(x interface{}) {
n := len(*pq)
item := x.(*Item)
item.index = n
*pq = append(*pq, item)
}
func (pq *PQ) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
old[n-1] = nil
item.index = -1
*pq = old[0 : n-1]
return item
}
|