狗店面

倒序浏览 · 2021-6-16 06:16:07

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

利口鹫菱舞变种秒了

follow

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

y O(1)
没想出来

匿名用户-CGYMS *2021-6-20 20:39:02* · 2021-6-20 20:39:02

follow-up要做到logN不可能吧　扫描一遍数组都需要O(N)了　楼主是不是题目还有什么条件　不然不可能的

djmiss

logN求解存在吗？
给1024个数，logN = 10,操作10次就排序完？剩下1000个数都不用看的？我觉得好像不太可能吧。。。

kashimoto

请问楼主 time complexity(OlogN) 怎么做到呢, 不知道顺序的话至少需要扫一遍吧，是不是O(NlogN)?

niananiananian

O(1)空间就是快排吧

匿名用户-DHZ9M *2021-6-16 07:01:44* · 2021-6-16 07:01:44

niananiananian 发表于 2021-6-16 06:55
O(1)空间就是快排吧

不是，快排没有办法做到stable

匿名用户-DHZ9M *2021-6-16 09:41:16* · 2021-6-16 09:41:16

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Falldawn

要求O(1)的要和面试官确实算不算call stack

djmiss

follow up keep relative order这个是什么意思？
比如3124？期望的输出是什么？2431？

匿名用户-DHZ9M *2021-6-16 14:04:39* · 2021-6-16 14:04:39

djmiss 发表于 2021-6-16 13:32
follow up keep relative order这个是什么意思？
比如3124？期望的输出是什么？2431？

对的，test case是3124的话要返回2431

侵权

logN 不存在吧？是nlogn?