如何解决数据结构设计最大频率栈问题?

网友投稿 248 2022-11-22

如何解决数据结构设计最大频率栈问题?

读完本文,可以去力扣解决如下题目:

895.最大频率栈(Hard)

我个人很喜欢设计特殊数据结构的问题,毕竟在工作中会经常用到基本数据结构,而设计类的问题就非常考验对基本数据结构的理解和运用。

class FreqStack {

// 在栈中加入一个元素 val

public void push(int val) {}

// 从栈中删除并返回出现频率最高的元素

// 如果频率最高的元素不止一个,

// 则返回最近添加的那个元素

public int pop() {}

}

比如下面这个例子:

FreqStack stk = new FreqStack();

// 向最大频率栈中添加元素

stk.push(2); stk.push(7); stk.push(2);

stk.push(7); stk.push(2); stk.push(4);

// 栈中元素:[2,7,2,7,2,4]

stk.pop() // 返回 2

// 因为 2 出现了三次

// 栈中元素:[2,7,2,7,4]

stk.pop() // 返回 7

// 2 和 7 都出现了两次,但 7 是最近添加的

// 栈中元素:[2,7,2,4]

stk.pop() // 返回 2

// 栈中元素:[2,7,4]

stk.pop() // 返回 4

// 栈中元素:[2,7]

这种设计数据结构的问题,主要是要搞清楚问题的难点在哪里,然后结合各种基本数据结构的特性,高效实现题目要求的 API。

那么,我们仔细思考一下 push 和 pop 方法,难点如下:

1、每次 pop 时,必须要知道频率最高的元素是什么。

2、如果频率最高的元素有多个,还得知道哪个是最近 push 进来的元素是哪个。

为了实现上述难点,我们要做到以下几点:

1、肯定要有一个变量 maxFreq 记录当前栈中最高的频率是多少。

2、我们得知道一个频率 freq 对应的元素有哪些,且这些元素要有时间顺序。

3、随着 pop 的调用,每个 val 对应的频率会变化,所以还得维持一个映射记录每个 val 对应的 freq。

综上,我们可以先实现 FreqStack 所需的数据结构:

class FreqStack {

// 记录 FreqStack 中元素的最大频率

int maxFreq = 0;

// 记录 FreqStack 中每个 val 对应的出现频率,后文就称为 VF 表

HashMap《Integer, Integer》 valToFreq = new HashMap《》();

// 记录频率 freq 对应的 val 列表,后文就称为 FV 表

HashMap《Integer, Stack《Integer》》 freqToVals = new HashMap《》();

}

其实这有点类似前文 手把手实现 LFU 算法,注意 freqToVals 中 val 列表用一个栈实现,如果一个 freq 对应的元素有多个,根据栈的特点,可以首先取出最近添加的元素。

要记住在 push 和 pop 方法中同时修改 maxFreq、VF 表、FV 表,否则容易出现 bug。

现在,我们可以来实现 push 方法了:

public void push(int val) {

// 修改 VF 表:val 对应的 freq 加一

int freq = valToFreq.getOrDefault(val, 0) + 1;

valToFreq.put(val, freq);

// 修改 FV 表:在 freq 对应的列表加上 val

freqToVals.get(freq).push(val);

// 更新 maxFreq

maxFreq = Math.max(maxFreq, freq);

}

pop 方法的实现也非常简单:

public int pop() {

// 修改 FV 表:pop 出一个 maxFreq 对应的元素 v

Stack《Integer》 vals = freqToVals.get(maxFreq);

int v = vals.pop();

// 修改 VF 表:v 对应的 freq 减一

int freq = valToFreq.get(v) - 1;

valToFreq.put(v, freq);

// 更新 maxFreq

if (vals.isEmpty()) {

// 如果 maxFreq 对应的元素空了

maxFreq--;

}

return v;

}

这样,两个 API 都实现了,算法执行过程如下:

嗯,这道题就解决了,Hard 难度的题目也不过如此嘛~

原文标题:数据结构基本功:设计最大频率栈

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:Hadoop之常用概念
下一篇:Linkis计算中间件部署过程记录
相关文章

 发表评论

暂时没有评论,来抢沙发吧~