LeetCodeのJavaScriptは第23題を解答します.K個の秩序チェーンを結合します.(Merge K Sorted Lists)

2543 ワード
Time:2019/4/10 Title:Merge K Sorted Lists Difficulty:Difficulty Author:小鹿
テーマ:Merge K Sorted Lists
Merge k sorted linked lists and return it as one sorted list.Analyze and describe its complexity.
k個の並べ替えチェーンを結合して、結合後の並べ替えチェーンを返します.アルゴリズムの複雑さを解析して説明してください.
Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
Solve:
πアルゴリズムの考え方
簡単に二つのシングルチェーン表に基づいた統合が完了したら、この問題に対して、考察点は分割アルゴリズムであり、もう一つの考察点は再帰的呼び出しであり、分治と同時に再帰的に解決されることが多いと思います.
1、本題はまとめて並べ替える思想によって、少し改造すれば解決できます.
2、配列中のチェーン表を分割すると、配列中のチェーン表の中間を分割し、それぞれを結合し、大きなチェーン表に統合することです.
πコード実現
/**
  * @param {number[]} nums
  * @return {number[]}
  *   ：   k    
  *     ：
  * 1）        
  * 2）        1  
  * 3）        2  
  * 4）         2  
  */
var mergeKLists = function(lists) {
    //   lists        
    if(lists.length == 0){
        return null;
    }else if(lists.length == 1){
        //         1  
        return lists[0];
    }else if(lists.length == 2){
        //         2  
        return mergeTwoLists(lists[0],lists[1]);
    }else{
        //          2  
        //         
        let middle = Math.floor(lists.length/2);
        //        
        let leftList = lists.slice(0,middle);
        let rightList = lists.slice(middle);
        //   、  、  
        return mergeTwoLists(mergeKLists(leftList),mergeKLists(rightList));
    }       
};
//      
var mergeTwoLists = function(l1, l2) {
    let result = null;

    //    
    if(l1 == null) return l2;
    if(l2 == null) return l1;

    //        
    if(l1.val < l2.val){
        result = l1;
        result.next = mergeTwoLists(l1.next,l2);
    }else{
        result = l2;
        result.next = mergeTwoLists(l2.next,l1);
    }
    
    //    
    return result;
};
π拡張:分割アルゴリズム
分割アルゴリズムは、しばしば再帰的に使用され、いわゆる分割アルゴリズムは、名前の意味を考慮して、分割して、最も基本的なアルゴリズムは、正規化と並べ替え、迅速な並べ替えに有用です.つまり、元の問題をn個の規模に分けて小さく、元の問題と似た構造のサブ問題を再帰的に解決し、その結果を統合すると、元の問題の解が得られる.
1、分割アルゴリズムは各層の操作に再帰する.
  • 分解:もとの問題を一連の問題に分解する.
  • 解決:再帰的に各サブ問題を解いて、もしサブ問題が十分小さいなら、直接解決します.
  • 合併:サブ問題の結果を元にまとめる.
    • 2、分割アルゴリズムが満たす条件
  • 分解できます.元の問題と分解された小さな問題は同じパターンを持っています.
  • は関連がありません.元の問題を分解したサブ問題は独立して解決できます.サブ問題の間には相関がありません.この点は分治アルゴリズムとダイナミックプランの明確な違いです.
  • 終了条件:分解終了条件を有する.
  • 合併は複雑すぎてはいけません.サブ問題を元の問題に統合してもいいです.この統合操作の複雑さはあまり高くないです.そうでないと、アルゴリズムの全体的な複雑さを減らす効果がありません.
    • 私の個人番号に注目してください.「平凡に甘んじない私たち」は自分でプログラミングした物語を記録しました.LeetCodeの他のテーマ解析、Github:https://github.com/luxiangqiang/JS-LeetCode
    【23】Date