滴滴三面几道算法题

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

相关推荐

各位牛友,我现在该考研还是继续冲秋招?个人情况:末9科班,人工智能专业,但是在计算机学院,该学的基本都学了。语言主要学校学的是c++,自己学了些java,但是比较深的八股都不会。计算机基础和算法都还可以,项目是黑马头条,学校大作业什么的感觉和要投的方向差比较多。暑期投的基本都是java,大概情况如下个人暑期实习总结:笔试:美团3.23号 3.2/5               拼多多3.24号 2.9/4         淘天 3.27号 2.2/3携程 3.28号 3.45/4            小红书 4.2号 ak                华为 4.10号 300分出头(发挥好差)灵犀互娱 4.13号 ak            钉钉 4.16号 ak                   阿里国际 4.18号 ak腾讯云智 4.19号 2/3           b站 4.20号 ak面试:腾讯:QQ后台 3.14一面,3.27二面挂teg云架构 3.29一面挂应用宝后台开发 4.16一面挂美团:3.26一面挂携程:4.7一面,4.12二面挂拼多多:4.11一面,4.20二面(感觉挂了)友友们,我这个情况要继续卷实习(感觉完全没机会了),准备秋招吗?还是说考研沉淀(考研计划本校)还有个疑问,感觉实习没啥机会了,不知名小厂实习对秋招有帮助吗,还是说找不到大厂实习就直接准备秋招
投递美团等公司10个岗位
点赞 评论 收藏
转发
点赞 15 评论
分享
牛客网
牛客企业服务