ソート1.Sort List


leetcode 148. Sort List
質問する
接続リストをO(n logn)に揃えます.
I/O例
  • 入力:4、2、1、3
  • 出力:1、2、3、4
  • に答える
    O(n log n)の時間的複雑さが制限されるため,複数のソート方法が用いられるため,ブールソートは用いられない.したがって,並べ替えと関数を内蔵する方法を用いて解くことができる.
    連結ソート
    class Solution:
        def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
            if l1 and l2:
                if l1.val > l2.val:
                    l1, l2 = l2, l1
                l1.next = self.mergeTwoLists(l1.next, l2)
            return l1 or l2
    
        def sortList(self, head: ListNode) -> ListNode:
            if not (head and head.next):
                return head
    
            half, slow, fast = None, head, head
            while fast and fast.next:
                half, slow, fast = slow, slow.next, fast.next.next
            half.next = None
    
            l1 = self.sortList(head)
            l2 = self.sortList(slow)
    
            return self.mergeTwoLists(l1, l2)
  • runtime: 572 ms
  • memory: 50.9 MB
  • ソートチーム
    class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            p = head
            lst: List = []
            while p:
                lst.append(p.val)
                p = p.next
    
            lst.sort()
    
            p = head
            for i in range(len(lst)):
                p.val = lst[i]
                p = p.next
            return head
  • runtime: 160 ms
  • memory: 30.1 MB
  • Python内蔵関数sort()を使用すると、直接集計ソートを実現するよりも実際のソート速度が速いことがわかります.
    リファレンス
    Pythonアルゴリズムインタビュー