《零基础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

}

原文地址：https://blog.csdn.net/qq_39728668/article/details/145137660

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！