面试一道编程题,求解

腾讯一道编程题
设置一个栈,实现push(),pop(),merge()三个方法
(1)push: 对栈a 或 栈b 压入一个元素num
(2)pop: 对栈a 或 栈b 弹出一个元素
(3)merge: 将栈a合并到栈b,并清空栈a  或 栈b合并到栈a,清空栈b, 要按push的时间顺序合并
a 或 b 可以当作一个输入参数
要求 merge方法的平均时间复杂度为O(1)
面试官提示说:merge以后就不用再merge了,我也没听懂
有大佬来解一下,说下思路吗?
#腾讯##笔试题目##春招##实习#
全部评论
我有一个歪点子,首先构造单向链表(头插法)  然后给每个节点初始标记a队列的为1,b队列的为2 merge就把a的范围设为3,b的范围设为4 这样出队的话a就出队<=当前范围的数(目前是1,2,3) b就出队==当前b范围的数(目前是4) 唯一的缺点就是pop的极限复杂度可能会高一点(不过你题目没有要求pop的复杂度为1)
点赞 回复 分享
发布于 2019-05-01 23:07
类似LRU的双向链表+hash记录节点位置?
点赞 回复 分享
发布于 2019-05-01 22:34
可不可以有三个栈  一个总的  一个a 一个b...   或者楼上的hash  平均时间复杂度  是均摊给每个元素么?
点赞 回复 分享
发布于 2019-05-01 22:49
双向链表构造链式栈,merge栈尾指针指向目标栈的表头?不知道可行否
点赞 回复 分享
发布于 2019-05-01 22:56
push的时间顺序是指什么呢,是针对全局的push时间顺序还是单个栈的Push时间顺序 a 1(第一次Push) 3(第三次Push) b 2(第二次Push) 3(第四次Push) 合并成 1 2 3 4 吗
点赞 回复 分享
发布于 2019-05-01 22:57
我觉得就是1 3和 2 4要合并成1234,用两个双向链表代替栈应该可以
点赞 回复 分享
发布于 2019-05-01 23:04
如果push的操作按时间戳依次是1,2,...的话, merge操作相当于把 1到当前x 所有的push操作都给了一个栈
点赞 回复 分享
发布于 2019-05-01 23:46
二楼那样完全没问题,但是要保证pop快,就还得用两个栈,再加上一个线性表存储合并过的序列,并标记它属于哪个栈,每次将a和b中元素合并之后都加入这个序列,这样合并n个元素,用O(n)次,每个元素只可能被合并一次,均摊到每次操作上,平均时间复杂度也就O(1)。然后push pop就按照栈的来
点赞 回复 分享
发布于 2019-05-02 10:25

相关推荐

10-16 22:56
门头沟学院 C++
1234567800:歌尔今年给211开14-15k吗,我本地人连面试都不给😂
点赞 评论 收藏
分享
评论
点赞
23
分享
正在热议
# 25届秋招总结 #
439711次浏览 4483人参与
# 春招别灰心,我们一人来一句鼓励 #
41326次浏览 523人参与
# 阿里云管培生offer #
119564次浏览 2219人参与
# 地方国企笔面经互助 #
7908次浏览 18人参与
# 虾皮求职进展汇总 #
113287次浏览 880人参与
# 实习,投递多份简历没人回复怎么办 #
2453574次浏览 34845人参与
# 北方华创开奖 #
107205次浏览 598人参与
# 实习必须要去大厂吗? #
55548次浏览 959人参与
# 同bg的你秋招战况如何? #
75024次浏览 547人参与
# 提前批简历挂麻了怎么办 #
149746次浏览 1975人参与
# 投递实习岗位前的准备 #
1195558次浏览 18545人参与
# 你投递的公司有几家约面了? #
33162次浏览 188人参与
# 双非本科求职如何逆袭 #
661735次浏览 7392人参与
# 机械人春招想让哪家公司来捞你? #
157584次浏览 2267人参与
# 如果公司给你放一天假,你会怎么度过? #
4708次浏览 53人参与
# 如果你有一天可以担任公司的CEO,你会做哪三件事? #
11184次浏览 253人参与
# 发工资后,你做的第一件事是什么 #
12333次浏览 61人参与
# 工作中,努力重要还是选择重要? #
35493次浏览 384人参与
# 参加完秋招的机械人,还参加春招吗? #
20068次浏览 240人参与
# 实习想申请秋招offer,能不能argue薪资 #
39197次浏览 314人参与
# 我的上岸简历长这样 #
451849次浏览 8086人参与
# 非技术岗是怎么找实习的 #
155829次浏览 2120人参与
牛客网
牛客企业服务