头条编程
对1-n的数进行字典排序，求排序后第m个数字是多少。(n<10^18) 求问有什么好的方法#字节跳动#
2016-09-28 21:55 哈尔滨工业大学 Java
关注
对1-n的数进行字典排序，求排序后第m个数字是多少。(n<10^18) 求问有什么好的方法#字节跳动#
全部评论
pxx11111
西北农林科技大学 安卓
没有同问
pxx11111
西北农林科技大学 安卓
我有个思路是把第一位相同的数保存下来，排序，归并数组，字典序应该是看第一位的
修改昵称中
北京大学 C++
我直接从第一个数字1，开始推下一个，一直推到第n个
修改昵称中
北京大学 C++
过了80%..没时间研究另外的20了了。。
rihkddd
北京化工大学 测试开发
大概有个思路，这个问题可以反着想，也就是给出一个数k，它是第几个，这个比较好做，从高位往下扫描，按长度从1到length(k)把结果累加，这样就很容易算出来了。这个复杂度是log(n)的.
然后是怎么从k是第几个反过来得到原问题的答案，很显然是要用二分的思想，但是并非所有的区间都有单调性，但是长度相同的是具有单调性的，所以算出根据m所在的区间先计算出答案的长度，然后在这个区间进行二分答案即可。
总体的复杂度是log(n) * log(n).
牛客615963号
国际关系学院 C++
可以看作一个十叉树，每个节点的子节点数量可以在lgN复杂度内求出，先从1到9累加节点数量，例如累加到5的时候发现超过m了，说明要找的数在5这颗子树里，重复上面的流程。最后复杂度也是lgN*lgN
拥有
浙江大学 Java
这个可以用快排的思想啊，首先第一个数找到对应的位置m，如果是k，结束；如果大于，在前一部分找；如果小于，在后一部分找k-m
thank
江西师范大学 Java
直接把输入的数字 循环转成集合，再用集合Collection.sort排序 然后获取集合的第k-1个元素，可惜不知道为什么只ac了40%。难道是算法时间内存不合格吗？
牛客8915991号
华南农业大学 C++
http://www.cnblogs.com/wshh/p/5921984.html
我笔试时也没做出来。dfs应该就行。复杂度应该不会超过（18×10×18）感觉。
相关推荐
投递vivo等公司10个岗位 > 点赞 评论 收藏
分享
点赞 评论 收藏
分享
腾讯公司福利 503人发布 点赞 评论 收藏
分享