这是LeetCode上的排序列表问题https://oj.leetcode.com/problems/sort-list/我制作了一个Java解决方案,但在一个非常长的测试用例中,它导致了Time Limit Exceeded。我在代码中找不到错误。有人能指出漏洞在哪里吗?非常感谢。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public class Solution {
public ListNode sortList(ListNode head) {
return this.sortPart(head, null);
}
private ListNode sortPart(ListNode start, ListNode end){
if(start == null)return null;
if(start == end)return start;
ListNode l=start, r=start, p=start.next;
while(p!= null && p!=end){
if(p.val < start.val){ // current node less than start node
r.next = p.next;
p.next = l;
l = p; // set current node as leftmost
p = start.next; // go to next node
}else{ // current node no less more start node
r = p; // set current node as rightmost and go to next node
p = p.next;
}
}
// recursively sort left part and right part
sortPart(l,start);
sortPart(start.next, r);
return l;
}
}
错误可能是已经排序的列表上的快速排序是O(n*n)
。一个实用的解决方案是随机选择枢轴。标准的在线储层采样算法解决了这一问题。
然而,这可能还不够好。Quicksort将创建一个带有O(log(n))
调用的调用堆栈,因此占用O(log(n))
空间。如果他们设置了足够好的测试,他们应该能够验证你已经完成了测试。
有关真正的解决方案,请参阅http://comjnl.oxfordjournals.org/content/35/6/643.full.pdf.
考虑到有多少人已经通过了这个问题,我怀疑他们没有准确地理解O(log(n))
空间和O(1)
空间之间的区别。
我不知道你为什么选择快速排序……最坏的情况是O(n*n)。。。。你要找的是堆排序O(n+n*log(n))方程。到O(nlog(n))并且具有O(1)的空间复杂度