头条编程
对1-n的数进行字典排序，求排序后第m个数字是多少。(n<10^18) 求问有什么好的方法#字节跳动#
2016-09-28 21:55 哈尔滨工业大学 Java
关注
对1-n的数进行字典排序，求排序后第m个数字是多少。(n<10^18) 求问有什么好的方法#字节跳动#
全部评论
牛客8915991号
华南农业大学 C++
http://www.cnblogs.com/wshh/p/5921984.html
我笔试时也没做出来。dfs应该就行。复杂度应该不会超过（18×10×18）感觉。
thank
江西师范大学 Java
直接把输入的数字 循环转成集合，再用集合Collection.sort排序 然后获取集合的第k-1个元素，可惜不知道为什么只ac了40%。难道是算法时间内存不合格吗？
拥有
浙江大学 Java
这个可以用快排的思想啊，首先第一个数找到对应的位置m，如果是k，结束；如果大于，在前一部分找；如果小于，在后一部分找k-m
牛客615963号
国际关系学院 C++
可以看作一个十叉树，每个节点的子节点数量可以在lgN复杂度内求出，先从1到9累加节点数量，例如累加到5的时候发现超过m了，说明要找的数在5这颗子树里，重复上面的流程。最后复杂度也是lgN*lgN
rihkddd
北京化工大学 测试开发
大概有个思路，这个问题可以反着想，也就是给出一个数k，它是第几个，这个比较好做，从高位往下扫描，按长度从1到length(k)把结果累加，这样就很容易算出来了。这个复杂度是log(n)的.
然后是怎么从k是第几个反过来得到原问题的答案，很显然是要用二分的思想，但是并非所有的区间都有单调性，但是长度相同的是具有单调性的，所以算出根据m所在的区间先计算出答案的长度，然后在这个区间进行二分答案即可。
总体的复杂度是log(n) * log(n).
修改昵称中
北京大学 C++
过了80%..没时间研究另外的20了了。。
修改昵称中
北京大学 C++
我直接从第一个数字1，开始推下一个，一直推到第n个
pxx11111
西北农林科技大学 安卓
我有个思路是把第一位相同的数保存下来，排序，归并数组，字典序应该是看第一位的
pxx11111
西北农林科技大学 安卓
没有同问
相关推荐
投递阿里巴巴集团等公司10个岗位 07-26 07:41
门头沟学院 C++ 点赞 评论 收藏
分享
06-14 11:09
电子科技大学 集成电路IC设计 点赞 评论 收藏
分享
07-29 16:49
门头沟学院 嵌入式软件开发 
RazerYang：其实也是幸存者偏差，你只关注草台班子的部分，所以觉得世界都是草台班子。实际上你每天能安全地从床上醒来，有稳定的天然气、自来水和电力供应，能让你吃上热乎的饭菜，能收到持续稳定的信号去刷手机，花几块钱就能坐地铁从城市的一端快速移动到另一端，花几百块就能在一天之内安全穿越整个国家，这都不是一个草台班子能实现的。燃气、水利、电力、通信、公交、民航，还有最重要的公安和国防，这些都不是草台班子能做的，有无数普通人构筑了你生活的方方面面，而你也将加入他们。 点赞 评论 收藏
分享