滴滴三面几道算法题

1、大数组,很多重复,怎么排序 2、1到n+2范围的数选n个组成一个数组,找少的那两个 第一个我答的桶排,第二个不会O(n)的。 怎么答?
全部评论
文艺做法:     设缺失的数为x和y,将原数组和数组{1,2,3,....,n,n+1,n+2}合并,得到一个长度为2n+2的数组Array。 求得Array[ 0 ]^Array[ 1 ]^...&Array[ 2n+1 ]的值V,则V=x^y。由于x!=y ,V肯定不为0。     随便选择一个二的次幂值m,使得V&m>0,比如V=0001001(2) ,则m可取1,8。     将Array中的元素分成2个数组,分组的依据为Array[ 1 ]&m>0及Array[ 1 ]&m=0。此种分法,必然将x和y分到2个数组中,且两个数组除x和y之外,其它的数组都是成对出现的。     将2个数组分别取异或(计算方式同于计算Array的值V),得到2个值,即为x和y。 2B做法:        定义一个长度为n+2的bool数组,对于数组的每个值,将bool中对应位置设为true,然后找到2个false的下标。 结论:         此题存在纰漏,而防止2B做法出现的方法应该是提供2个数组,第2个数组比第一个少了2个元素,设计算法找出少的2个元素。
点赞 回复 分享
发布于 2017-09-22 13:38
第二个用bit把
点赞 回复 分享
发布于 2017-09-22 13:25
设缺失的两个数为x,y 则 1+2+3+...+(n+1)+(n+2)=S1 (固定常数) 1^2+2^2+3^2+...+(n+1)^2+(n+2)^2=S2 (固定常数) 则对给定的数组,其全部元素和为M1,全部元素平方和为M2 则有 x+y+M1=S1 x^2+y^2+M2=S2 解出x和y即可
点赞 回复 分享
发布于 2017-09-22 13:25
我和你的第二题一样,我给出的思路是这样的,给数组排号,数组为1到n号,数字1放在1号位置,数字2放在2号位置,以此类推,n+1和n+2设置为两个false的布尔类型,如果数组中出现n+1和n+2,就把对于的bool设置为ture,把出现n+1或者n+2的位置设置为0。整体思想就是给数组编号,然后里面的数字对号入座。这样是O(n)的复杂度,O(1)的空间复杂度。我当时答完三面就过了。
点赞 回复 分享
发布于 2017-09-22 13:31
第一个计数排序
点赞 回复 分享
发布于 2017-09-22 14:49
比如对全国考研数学成绩排序
点赞 回复 分享
发布于 2017-09-22 14:50
大佬,能否把这两个题目描述清楚点啊,没太看懂题目
点赞 回复 分享
发布于 2017-10-06 19:58

相关推荐

点赞 评论 收藏
分享
01-23 15:45
已编辑
门头沟学院 DBA
双休五险一金:喜欢年会的小蛇仔仔
点赞 评论 收藏
分享
面经加本人真实所感,虽然基本上都是小厂,但是希望也能给诸位做一个参考厨芯-产品经理一面共十五分钟自我介绍秋招时是否有拿offer复盘过往经历你对产品经理这个职业的看法为什么会想到做产品经理你觉得自己在产品经理这一方向有何优势你觉得自己还有什么可以提升的方面个人职业规划心怡城市目标薪资反问(感觉面试官后面明显失去兴趣了,悲,前面我都答上来了,还说我答的挺好的,一到职业规划部分态度就变了,下次多注意吧。)众阳健康-数据分析一面hr、面试官人都挺好的,我没答上来的都给我讲解了,目前体验最好的一次:面试时间半小时自我介绍学过哪些数据库数据库模型都有哪些数据库索引是什么有哪些情况会导致索引失效数据分析都有哪些方法说一说归因分析面向对象的编程语言和面向过程的编程语言有什么区别python浅拷贝和深拷贝的区别如果给你一份各个医院的数据,让你给这些医院做个排名,你会如何分析(情景题)反问:因为面试官也是跟我同专业的所以让他给我的职业规划提一点建议,他说干什么都好,一定不要干测试🙂我:受教!科益虹源-测开面试体验:差劲,不仅迟到还敷衍,hr和面试官都是一点专业问题没问:自我介绍介绍一下做过的测试项目介绍一下之前做过的数分项目接受在车间做系统测试吗无反问环节像kpi,没见过这样的 #牛客创作赏金赛# #面试中的破防瞬间# #非技术面试记录# #现在还是0offer,延毕还是备考# #牛客激励计划# #面试体验感最好的是哪家?#
点赞 评论 收藏
分享
评论
点赞
15
分享

创作者周榜

更多
牛客网
牛客企业服务