用O(1)空间复杂度对O(n-logn)中的链表进行排序



这是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)的空间复杂度

相关内容

  • 没有找到相关文章