头条编程


对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

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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