面试一道编程题，求解

腾讯一道编程题
设置一个栈，实现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

相关推荐

不愿透露姓名的神秘牛友
11-29 22:16
点赞 评论 收藏
分享
头像
11-25 16:11
牛客运营
原来面试要靠演技
别误会，这里的“演技”不是指欺骗或者虚假，而是指我们需要学会在面试中更好地展示自己，让自己更加符合招聘方的需求。“演技”，在这个语境下，更多的是指一种自我提升的过程。通过参加更多的模拟面试，你可以学习到如何更准确地表达自己的想法，如何在紧张的环境中保持冷静，甚至是如何根据面试官的问题灵活调整自己的答案。这个过程不仅能帮助你更好地了解自己，也能让你在真实的面试中更加自信。牛牛近期推出的【牛客&nbsp;·&nbsp;模拟面试活动】非常适合当下准备面试的应届生们，点击下方链接或扫码，不收费，邀请2位同学组团，即可一起免费参与！不影响其他面试结果，还有面试报告可用及时查缺补漏。拿offer，别犹豫，点击马...
点赞 评论 收藏
分享
11-13 20:32
门头沟学院 Java
问一下是不是外包岗就急眼了
说好的了解呢？我没歧视外包啊
面向未来编程code：我没看到他咋急，他不就问你个问题。。。
点赞 评论 收藏
分享
11-18 10:36
内蒙古民族大学 Java
二本实习简历，初筛都过不去
狠狠的赚一笔😋
听说改名字就能收到offer哈：Radis写错了兄弟
点赞 评论 收藏
分享
11-27 17:08
已编辑
牛客_产品运营部_私域运营
解码！2025届校招白菜、sp、ssp薪资档位公开！
腾讯 普通offer 24k～26k * 15，年包在36w～39w左右。
点赞 评论 收藏
分享
评论
点赞
23
分享

招聘动态

查看更多

快手

2025届招聘即将截止

阿里云管培生

2025届校园招聘

富士通（西安）

2025校园招聘

全站热榜

正在热议
# 25届秋招总结 #
440279次浏览 4490人参与
# 春招别灰心，我们一人来一句鼓励 #
41427次浏览 524人参与
# 阿里云管培生offer #
119720次浏览 2219人参与
# 地方国企笔面经互助 #
7916次浏览 18人参与
# 虾皮求职进展汇总 #
113709次浏览 881人参与
# 实习，投递多份简历没人回复怎么办 #
2453837次浏览 34847人参与
# 北方华创开奖 #
107270次浏览 599人参与
# 实习必须要去大厂吗？ #
55563次浏览 960人参与
# 同bg的你秋招战况如何？ #
75364次浏览 551人参与
# 提前批简历挂麻了怎么办 #
149798次浏览 1977人参与
# 投递实习岗位前的准备 #
1195641次浏览 18546人参与
# 你投递的公司有几家约面了？ #
33170次浏览 188人参与
# 双非本科求职如何逆袭 #
661802次浏览 7394人参与
# 机械人春招想让哪家公司来捞你？ #
157587次浏览 2267人参与
# 如果公司给你放一天假，你会怎么度过？ #
4719次浏览 54人参与
# 如果你有一天可以担任公司的CEO，你会做哪三件事？ #
11300次浏览 267人参与
# 发工资后，你做的第一件事是什么 #
12368次浏览 61人参与
# 工作中，努力重要还是选择重要？ #
35576次浏览 384人参与
# 参加完秋招的机械人，还参加春招吗？ #
20072次浏览 240人参与
# 实习想申请秋招offer，能不能argue薪资 #
39220次浏览 314人参与
# 我的上岸简历长这样 #
451897次浏览 8088人参与
# 非技术岗是怎么找实习的 #
155832次浏览 2120人参与
牛客网
牛客企业服务