狗店面

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

不好意思写错了，follow up是NLogN

匿名者 发表于 2021-6-20 20:39
follow-up要做到logN不可能吧　扫描一遍数组都需要O(N)了　楼主是不是题目还有什么条件　不然不可能的

不好意思写错了，是NlogN

侵权 发表于 2021-6-19 09:41
logN 不存在吧？是nlogn?

不好意思写错了，是NlogN

额 这不可能吧...请问楼主fail了吗

iuysyjdmuvew 发表于 2021-6-29 09:48
额 这不可能吧...请问楼主fail了吗

是的，fail了

不能用房built-in function ,我觉得真难

https://www.geeksforgeeks.org/stability-in-sorting-algorithms/

https://en.wikipedia.org/wiki/Ca ... ms%20maintain%20the,S%20in%20the%20sorted%20list.

和楼主面到了一样的题目，最后根据提示做完了。followup的话时间复杂度是O(n^2)，用bubble sort，可以让空间复杂度为O(1).最后面试官带着我分析了一下为什么要O（n^2），原因是其他的sort不能保证相对的顺序。。。

maintain relative order，time O(N), space O(1)应该行吧? 至少time O(N), space O(N)可以。