2019-05-01 22:10 西安电子科技大学算法工程师

关注

面试一道编程题，求解

腾讯一道编程题

设置一个栈，实现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了，我也没听懂

有大佬来解一下，说下思路吗？

#腾讯##笔试题目##春招##实习#

全部评论

推荐最新楼层

被咬过的包子

门头沟学院 Java

我有一个歪点子，首先构造单向链表（头插法) 然后给每个节点初始标记a队列的为1,b队列的为2 merge就把a的范围设为3，b的范围设为4 这样出队的话a就出队<=当前范围的数（目前是1,2，3） b就出队==当前b范围的数（目前是4）唯一的缺点就是pop的极限复杂度可能会高一点（不过你题目没有要求pop的复杂度为1）

点赞回复分享

发布于 2019-05-01 23:07

ChessC

浙江大学 Java

类似LRU的双向链表+hash记录节点位置？

点赞回复分享

发布于 2019-05-01 22:34

只是个废柴

中国矿业大学 golang

可不可以有三个栈一个总的一个a 一个b... 或者楼上的hash 平均时间复杂度是均摊给每个元素么？

点赞回复分享

发布于 2019-05-01 22:49

Everything_will_be_ok

门头沟学院 Java

双向链表构造链式栈，merge栈尾指针指向目标栈的表头？不知道可行否

点赞回复分享

发布于 2019-05-01 22:56

被咬过的包子

门头沟学院 Java

push的时间顺序是指什么呢，是针对全局的push时间顺序还是单个栈的Push时间顺序 a 1(第一次Push) 3(第三次Push) b 2(第二次Push) 3(第四次Push) 合并成 1 2 3 4 吗

点赞回复分享

发布于 2019-05-01 22:57

YanXiaosi

University of Southern California Java

我觉得就是1 3和 2 4要合并成1234，用两个双向链表代替栈应该可以

点赞回复分享

发布于 2019-05-01 23:04

Maggch

北京化工大学 Java

如果push的操作按时间戳依次是1,2,...的话, merge操作相当于把 1到当前x 所有的push操作都给了一个栈

点赞回复分享

发布于 2019-05-01 23:46

newcode123

哈尔滨工业大学 C++

二楼那样完全没问题，但是要保证pop快，就还得用两个栈，再加上一个线性表存储合并过的序列，并标记它属于哪个栈，每次将a和b中元素合并之后都加入这个序列，这样合并n个元素，用O(n)次，每个元素只可能被合并一次，均摊到每次操作上，平均时间复杂度也就O(1)。然后push pop就按照栈的来

点赞回复分享

发布于 2019-05-02 10:25

11-23 11:10

北京航空航天大学前端工程师

网易实习四个月体验

上班时间是10点到18点半，中午有两个小时的午休，算下来每天工作也就六个半小时。我所在的组任务量刚刚好，四个月里从来没有加过班。不过听说有些组的同事就没那么幸运，吃饭的时候有哥们说他连续三周都在加班。同事们都特别友好，几乎每周都有免费的下午茶，大家一起聊天，气氛超好。还有，网易严选的员工购物打三折，花了90多块买了300多的东西，很划算

网易公司福利 162人发布

点赞评论收藏

11-25 00:18

华东师范大学策略运营

终于结束秋招了！

今天三方协议流程结束，意味着我的秋招也画上了句号。感谢坚持不懈的自己，辛苦了！无论未来如何变化，我相信一切都是最好的安排。继续加油吧！

牛客创作赏金赛

点赞评论收藏

10-05 07:57

门头沟学院后端

🐭🐭9月速拿5个oc

秋招不易，收了5个oc，却收了50多封感谢信😭😋已oc😋字节腾讯美团科大讯飞中兴😉等oc😉快手滴滴京东😭三面挂😭TME百度度小满😭😭一二面挂😭😭小红书米哈游😭😭😭简历挂😭😭😭阿里云淘天阿里国际灵犀互娱达摩院蚂蚁旷视商汤大疆地平线西山居momentabilibilioppovivo荣耀蔚来tplink普联tplink联洲

ProMonkey2024：5个oc？厉害！但是有一个小问题：谁问你了？😡我的意思是，谁在意？我告诉你，根本没人问你，在我们之中0人问了你，我把所有问你的人都请来 party 了，到场人数是0个人，誰问你了？WHO ASKED？谁问汝矣？誰があなたに聞きましたか？누가 물어봤어？我爬上了珠穆朗玛峰也没找到谁问你了，我刚刚潜入了世界上最大的射电望远镜也没开到那个问你的人的盒，在找到谁问你之前我连癌症的解药都发明了出来，我开了最大距离渲染也没找到谁问你了我活在这个被辐射蹂躏了多年的破碎世界的坟墓里目睹全球核战争把人类文明毁灭也没见到谁问你了（别的帖子偷来的，现学现卖😋）

点赞评论收藏