头条编程


对1-n的数进行字典排序,求排序后第m个数字是多少。(n<10^18) 求问有什么好的方法#字节跳动#
全部评论
http://www.cnblogs.com/wshh/p/5921984.html 我笔试时也没做出来。dfs应该就行。复杂度应该不会超过(18×10×18)感觉。
点赞 回复 分享
发布于 2016-09-29 21:36
直接把输入的数字  循环转成集合,再用集合Collection.sort排序  然后获取集合的第k-1个元素,可惜不知道为什么只ac了40%。难道是算法时间内存不合格吗?
点赞 回复 分享
发布于 2016-09-29 15:15
这个可以用快排的思想啊,首先第一个数找到对应的位置m,如果是k,结束;如果大于,在前一部分找;如果小于,在后一部分找k-m
点赞 回复 分享
发布于 2016-09-29 01:34
可以看作一个十叉树,每个节点的子节点数量可以在lgN复杂度内求出,先从1到9累加节点数量,例如累加到5的时候发现超过m了,说明要找的数在5这颗子树里,重复上面的流程。最后复杂度也是lgN*lgN
点赞 回复 分享
发布于 2016-09-29 00:16
大概有个思路,这个问题可以反着想,也就是给出一个数k,它是第几个,这个比较好做,从高位往下扫描,按长度从1到length(k)把结果累加,这样就很容易算出来了。这个复杂度是log(n)的. 然后是怎么从k是第几个反过来得到原问题的答案,很显然是要用二分的思想,但是并非所有的区间都有单调性,但是长度相同的是具有单调性的,所以算出根据m所在的区间先计算出答案的长度,然后在这个区间进行二分答案即可。 总体的复杂度是log(n) * log(n).
点赞 回复 分享
发布于 2016-09-28 23:31
过了80%..没时间研究另外的20了了。。
点赞 回复 分享
发布于 2016-09-28 22:39
我直接从第一个数字1,开始推下一个,一直推到第n个
点赞 回复 分享
发布于 2016-09-28 22:37
我有个思路是把第一位相同的数保存下来,排序,归并数组,字典序应该是看第一位的
点赞 回复 分享
发布于 2016-09-28 22:07
没有同问
点赞 回复 分享
发布于 2016-09-28 22:03

相关推荐

时间线:&nbsp;1.4-1.5:&nbsp;boss&nbsp;牛客&nbsp;官网&nbsp;实习僧海投了两天,&nbsp;感觉确实没啥招人的啊,&nbsp;心里凉了一半.1.6:&nbsp;中午快手约面,&nbsp;下午字节hr飞书私聊约面,&nbsp;当时想着第一次面大厂感觉三个过一个一面就已经赢了.1.7:&nbsp;下午&nbsp;3点大厂处女面,&nbsp;哈哈面试官是重邮红岩的直接保送;&nbsp;5点快手一面,&nbsp;我说这个是我的第二次大厂面试,&nbsp;面试官问要是拿到字节和快手选择哪个,&nbsp;我说昨天看了一晚上快手百分百选快手哈哈哈.&nbsp;晚上5.30字节约二面,&nbsp;快手约二面,&nbsp;小红书约一面.1.8:&nbsp;下午2点快手二面,&nbsp;聊天面体验非常好(当天电话确认入职时间);&nbsp;4点字节二面这次不是校友了,&nbsp;然后有一个CSS实现switch效果的忘记属性咋写了,&nbsp;感觉危了;&nbsp;7.30&nbsp;问字节hr是不是挂了;&nbsp;9点开始小红书一面,&nbsp;难死我了,&nbsp;但我还是笑着面完了,&nbsp;然后卸载了小红书,&nbsp;但是过了一会会小红书hr约二面,&nbsp;遂下回来了字节约三面.1.9:&nbsp;下午2点字节三面,&nbsp;依旧聊天+算法,&nbsp;自己太菜了有一个写错了,&nbsp;面完感觉又危了;&nbsp;5点面小红书20min结束(offer审批);5.30又去问字节hr是不是挂了,&nbsp;hr小姐姐说干嘛用一个句式,&nbsp;我说手写题又又又没写出来😂,&nbsp;2min后约hr面;8.30&nbsp;快手offer总结,&nbsp;自己运气好遇到了好公司好部门好面试官,&nbsp;字节剪映&nbsp;快手电商&nbsp;小红书支付的面试体验都非常好,&nbsp;不会的题会带你一步一步思考,&nbsp;流程也非常快全部都是当天推进,&nbsp;小红书是以分钟为单位推进.&nbsp;&nbsp;面经以及细节等我慢慢整理,&nbsp;&nbsp;以及保佑所有的审批不要出问题,&nbsp;我是真怕最后全过了0offer😂bg:&nbsp;重邮&nbsp;大数据&nbsp;蓝山工作室&nbsp;一段非大厂实习
独角仙梦境:这是真👻了
找实习记录
点赞 评论 收藏
分享
牛客98820962...:个人意见,我觉得实习和项目经历要一致,达美乐感觉没必要写
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务