leetcode sortList

北美农民 发表于 2014-8-2 09:02
bottom up不tricky， 只是要一份implementation看看写的怎么样， 感觉很乱。

我记得在哪里看过真正应 ...

我就是说实现很tricky……思想当然简单……

Kimurate 发表于 2014-8-2 12:11
我就是说实现很tricky……思想当然简单……

我仔细读了一下这个非递归的版本， 直觉上这个版本的代价是基于一些常数时间复杂度代价的（最里层1 - interval的循环）， 还有一些不好计算overhead。 为了验证猜测我提交测了一下， 比我的递归版本要慢了100+ 毫秒。

0 minutes ago        Accepted        472 ms        java
1 minute ago        Accepted        580 ms        java

一般来说递归进栈出栈需要的时间代价更大，空间复杂度logn更高那么对内存的开辟消耗也更多， 所以非递归版本速度一般是要高于递归版本，但是这个例子中为了实现理论上O(1)的空间而导致速度上反而不如，感觉失去了初衷。不知道还有更好或者更简洁的非递归实现版本没有， 我猜用一个(head, end)的二元组数据结构表示链表会有更好的效果。

北美农民 发表于 2014-8-2 10:10
我仔细读了一下这个非递归的版本， 直觉上这个版本的代价是基于一些常数时间复杂度代价的（最里层1 - int ...

merge sort 里应该没法避免 1 - interval 的循环吧。
话说，leetcode那个时间不太准的，同一段代码的执行时间都可以差100ms以上，很难作为评判标准…

北美农民 发表于 2014-8-3 00:16
对了， 求一段 nlogn排序 + 常数空间的实现？  谢谢。

这个我也没写出来还，不过用non-recursion的merge sort应该可以