头条编程


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

相关推荐

团队介绍:字节跳动系统部,负责字节跳动从芯片到服务器、操作系统、网络、CDN&nbsp;、数据中心等基础设施的研发、设计、采购、交付与运营管理,为包含抖音、头条、火山引擎等全球业务提供高效、稳定、具备可扩展性的基础设施。部门当前业务开展包括不限于:数据中心设计建设、芯片研发、服务器研发、网络工程研发、火山引擎边缘云业务、高性能智能硬件研发、IDC资源智能交付与运维、硬件基础设施智能监控与预警、操作系统与内核、虚拟化技术、编译工具链、供应链管理等众多基础设施相关方向。1、参与系统平台的前端开发工作,包括交付规划,资源管理,运维运营,商务成本,基础服务等;2、参与技术能力沉淀和演进,包括业务组件库,流程系统,搭建平台无线化,站点编排等。--------职位要求1、2025届获得本科及以上学历,计算机、软件工程等相关专业优先;2、逻辑严谨,善于倾听,表达清晰,乐于协作,责任心强,学习能力强;3、有扎实的计算机基础,有良好的方案设计能力和编码习惯;4、对技术有热情,对行业主流方案和新趋势有关注和思考;5、掌握Web前端开发相关基本技能:NPM,JavaScript/TypeScript,React/Vue,&nbsp;NodeJS,Koa等;6、加分项:有完整的个人作品,给知名开源项目提交代码,参与知名技术竞赛等。办公地点:北京$海淀区大钟寺广场2号楼&nbsp;&nbsp;/&nbsp;杭州$余杭区EFC英国中心投递:私聊发我&nbsp;or&nbsp;邮箱&nbsp;wangshengsong@bytedance.com,帮你review简历
投递字节跳动等公司10个岗位
点赞 评论 收藏
分享
小红书 多模态大模型算法 300-400 一天
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务