蓝鸟电面挂经

倒序浏览 · 2021-9-22 00:00:57

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

设计一个数据结构支持add(ele), remove(idx), getLast(), getRandom()操作。和力扣上的某题相似，但是不同

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

持getRandom/remove操作。

求大米。求安慰。求大米。求安慰。

来自APP · 2021-9-22 07:45:23

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-R1ECC *2021-9-22 01:22:17* · 2021-9-22 01:22:17

加一个queue。每次remove时同时把被remove的index入queue， O1。getLast要先check queue非空的话返回队列头的index指向的元素。queue是空时才返回数据数组最后一个元素。

biomedicineman

需要返回最后插入的元素...

指的是上一次add(ele)操作加入的element吗？
所以要在LC380这道题基础上，再加一个doubly linkedlist来保存add的顺序

挖煤

推特特别慢不一定不给过

来自APP · 2021-9-22 07:49:57

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

匿名用户-R1ECC *2021-9-22 10:00:57* · 2021-9-22 10:00:57

匿名者发表于 2021-9-21 19:49
对的，我后来就是这么做的，一切和利口上的一样，就是在getLast的时候用doubly linked list取尾部节点。
...

你用list存双链表的node？那应该就是O1的最优解了.

jmssg5166101 · 2021-11-24 17:41:03

这个数据结构可能会有相同的元素吗？

jmssg5166101 · 2021-11-24 17:59:07

这个remove(idx)怎么实现O(1)的啊？LC380里面是remove(val)

hermannitty · 2021-11-24 18:40:29

所以楼主过了吗