《零基础Go语言算法实战》【题目 4-2】使用 Go 语言实现一个模拟栈数据结构操作的类 FrequencyStack
《零基础Go语言算法实战》
【题目 4-2】使用 Go 语言实现一个模拟栈数据结构操作的类 FrequencyStack
FrequencyStack 有两个功能：push(int x) 方法将整数 x 压入栈，pop() 方法将栈中出现频次
最高的元素删除并返回；如果出现频次最高的元素存在相同的数量，则最接近栈顶部的元素
将被删除并返回。
【解答】
package main
import "fmt"
type FrequencyStack struct {
freq map[int]int
group map[int][]int
maxfreq int
}
func NewFrequencyStack() FrequencyStack {
hash := make(map[int]int)
maxHash := make(map[int][]int)
return FrequencyStack{freq: hash, group: maxHash}
}
func (fs *FrequencyStack) Push(x int) {
if _, ok := fs.freq[x]; ok {
fs.freq[x]++
} else {
fs.freq[x] = 1
}
f := fs.freq[x]
if f > fs.maxfreq {
fs.maxfreq = f
}
fs.group[f] = append(fs.group[f], x)
}
func (fs *FrequencyStack) Pop() int {
tmp := fs.group[fs.maxfreq]
x := tmp[len(tmp)-1]
fs.group[fs.maxfreq] = fs.group[fs.maxfreq][:len(fs.group[fs.maxfreq])-1]
fs.freq[x]--
if len(fs.group[fs.maxfreq]) == 0 {
fs.maxfreq--
}
return x
}