58. Sort List

11133 ワード
アルゴリズム#アルゴリズム# テキストリンク
道しるべ
  • 接続リストをO(nlogn)で
    • に並べ替える


    1.集計ソート(320ミリ秒)

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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)

  • これは、接続リストを入力値として使用するため、直接ソートを実現する必要がある良い問題です.
  • しかし,時間的複雑さはO(nlogn)で解決しなければならないという制約もある.

  • 接続リスト入力についてはPythonでソートできる個別の関数はないため,直接ソートアルゴリズムを実現する必要がある.

  • 入力値-1->5->3->4->0接続リストの集計ソート手順を以下に示します.


  • ソートされた分割征服を統合するためには,中央を分割する必要がある.
  • 図にも5を基準とした分割過程が現れている.

  • ただし,接続リストは全長が分からないため,ここではrunnerテクニックを用いた.
  • half, slow, fast3変数を作成し、slowを1つ前進させ、fastを2つ前進させます.

  • これにより、fastが先端に到達すると、slowは中央に到達する.
  • halfはslowの正遷移値である.

  • 最後にhalf.next = Noneであり、halfの位置を基準として接続リスト関係を切断する.

  • 分割後に再帰呼び出しを行います.
  • headは開始ノードであり、slowは探索によって発見された中心点である.

  • 図3はslowである.

  • この値を基準として再帰呼び出しを続けると、最終接続リストは-1、5、3、4、0の単一項目に分割されます.

  • 最後に、最終的に分割されたアイテムを再結合して返します.

  • 単純なマージではなくサイズを比較することでソートします.
  • mergeTwoLists()メソッドは、長さにかかわらず、l1を移動するポインタを再帰的に呼び出し、ソートを返す接続リストを入力値として受け入れる.

  • ここで、return l1 or l2の値がl1であれば、常にl1を返し、l1の値がNoneであればl2を返します.
    まず
  • すなわちl1である.

  • 前の2つのソートリストのマージ問題は必ずしもl1 or l2を比較する必要はありません.l1がNoneであれば、事前に交換する方法であり、どのように解いても結果は同じです.
    • <集計ソートを実施する最後の比較フェーズ>


  • 当初、l1のうち−1、l2のうちの0は入力値であり、l1のうちのnextのうちの5は0より大きいので、交換が行われる.

  • その後は交換せず、nextの順で3,4に接続し続けた.

  • 最後に、4のnextはNoneであり、この場合、return l1 or l2の部分はl2の値、すなわち5を返す.

  • 再呼び出しされた部分に遡ると,−1>0−>3−>4−>5と決定され,最終的なソートは良好に行われた.

    • 2.クイックソート（タイムアウト）


  • この問題を仮想パーティションなどの従来の高速ソートアルゴリズムで実現すると、タイムアウトが発生し、解決できません.
  • の高速ソートをさらに最適化してこそ、解を求めることができる.

  • Pythonでは、タイムアウトして解析できませんがjavaとC++は解析できますが、マージソートよりも時間がかかります.

  • 1、2、3段の3項目からなる1000個の入力値のテスト例があり、この部分ではPythonのクイックソートがタイムアウトし続けている.

  • 高速ソートは典型的な不安定なソートであり、同じ値を繰り返しても交換を試み続けます.

  • 接続リストは、プロパティ上の任意のピボットを指定することが困難なため、ここでは常にピボットを最初の値に設定します.この場合、ソートされたリストが入力値として使用されると、バランスのとれたリストに分割され続け、最悪の結果が表示されます.

  • これも、高速ソートが入力値によってパフォーマンスのばらつきが大きく、処理が困難なため、パフォーマンスが良くても実際の作業ではあまり使用されない理由です.

    • 3.組み込み関数を使用するための実用的な方法(84 ms)

    
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
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

  • この問題はソートアルゴリズムを直接実現する必要はない.
    多くのプログラミング言語が標準ライブラリでパフォーマンスの良いソートアルゴリズムを提供しているためです.

  • 実行時間をさらに短縮する必要がある符号化テストでは,これが最も賢明な方法であり,実際の作業では当然この方法も用いられる.

  • ホワイトボードにアルゴリズムを記述する必要がある場合は、避けるべきです.

  • 君は代弁したほうがいい.

  • インプリメンテーションコード

  • 接続リストをPythonのリストとして作成します.

  • Pythonの組み込みソート関数sort()について、次の操作を行います.

  • 並べ替えられたリストを接続リストとして再リストします.

  • ここでpはポインタです.

  • ポインタ変数は、接続リストを巡回するためにpに設定され、巡回およびチャージの役割を果たす.

  • 次に、ルートノードheadに戻る.

  • この解答は84 ms以内に完成することができ、最も簡単で、直観的で、容易である.
  • の他の制限事項がなければ、賢明に利用する必要がある.
    • プロジェクトレベルのgitconfigの設定
    楽しみのためにArgoトンネルと容器で単純なポートフォリオを展開すること🚀 - 第1部