How to improve O(n^2) python algorithm to ac


  • 0
    I

    I have implemented a typical O(n^2) insertion sort for this problem, however I got TLE on large inputs, when I tried the large input on my desktop, the result is correct. So I am wondering how can I improve the O(n^2) algorithm so that it meets OJ's timing threshold.

    class Solution:
    # @param head, a ListNode
    # @return a ListNode
    def insertionSortList(self, head):
        if not head: return None        # no node
        if not head.next: return head   # only 1 node
        if not hasattr(head, "next"): return None   # head is not a ListNode
        # consider head as the last element of the sorted list
        last = head
        # we start from head.next
        curr = last.next
        while curr:
            # if last.next > last, it means last.next is sorted as well
            if curr.val >= last.val:
                last = curr
                curr = last.next
                continue
            # start from insert_loc = head, if insert_loc >= curr, insert it
            insert_loc = head
            insert_loc_previous = None
            # find the location to insert
            while curr.val > insert_loc.val and insert_loc_previous != last:
                insert_loc_previous = insert_loc    # pointer to the previous
                insert_loc = insert_loc.next
            if not insert_loc_previous:         # insert_loc is head
                temp = curr.next
                curr.next = head
                head = curr
                last.next = temp
            else:                   # insert in the middle of the sorted list
                temp = curr.next
                curr.next = insert_loc
                insert_loc_previous.next = curr
                last.next = temp
            curr = last.next
        return head

  • 0
    B

    I used python and got an AC. For my code, I pre-processed the list to check whether it is sorted, which kinda of avoiding the worst case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.