面试一道编程题,求解

腾讯一道编程题
设置一个栈,实现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-09 00:50
已编辑
长江大学 算法工程师
不期而遇的夏天:1.同学你面试评价不错,概率很大,请耐心等待;2.你的排名比较靠前,不要担心,耐心等待;3.问题不大,正在审批,不要着急签其他公司,等等我们!4.预计9月中下旬,安心过节;5.下周会有结果,请耐心等待下;6.可能国庆节前后,一有结果我马上通知你;7.预计10月中旬,再坚持一下;8.正在走流程,就这两天了;9.同学,结果我也不知道,你如果查到了也告诉我一声;10.同学你出线不明朗,建议签其他公司保底!11.同学你找了哪些公司,我也在找工作。
点赞 评论 收藏
分享
评论
点赞
23
分享
牛客网
牛客企业服务