LeetCode 之 JavaScript 解答第23題 —— 合并K個有序鏈表（Merge K S

zhou_you 發布于2019-08-23 16:53 / 2046人閱讀

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關聯原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別。

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 倉庫，可以向 me 提交您其他語言的代碼。在倉庫上堅持和小伙伴們一起打卡，共同完善我們的開源小倉庫！
Github：https://github.com/luxiangqia...

云服務器 GPU云服務器合并鏈表的c語言第K順序 kafka數據有序無序找出第k大的數

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/103456.html

LeetCode 之 JavaScript 解答第21題 —— 合并兩個有序鏈表（Merge Two

摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數的參數和返回值是什么參數是兩個合并的鏈表結點頭結點。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿題目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 評論0 收藏0
JS算法題之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取。回文數題目描述判斷一個整數是否是回文數。回文數是指正序從左向右和倒序從右向左讀都是一樣的整數。 JS算法題之leetcode(1~10) 前言一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

SoapEye 2019-08-26 10:44 評論0 收藏0
第7期 Datawhale 組隊學習計劃

馬上就要開始啦這次共組織15個組隊學習涵蓋了AI領域從理論知識到動手實踐的內容按照下面給出的最完備學習路線分類難度系數分為低、中、高三檔可以按照需要參加 - 學習路線 - showImg(https://segmentfault.com/img/remote/1460000019082128); showImg(https://segmentfault.com/img/remote/...

dinfer 2019-06-26 18:55 評論0 收藏0
PHPer也刷《劍指Offer》之鏈表

摘要：劍指中鏈表相關題目俗話說光說不練假把式，既然學習了鏈表的基礎概念和基本操作那我們一定要找些題目鞏固下，下面來看劍指中的相關題目。題目分析合并兩個排序的鏈表，需要分別比較兩個鏈表的每個值，然后改變指針。溫故知新鏈表由一個一個的作為節點的對象構成的，每一個節點都有指向下一個節點的指針，最后一個節點的指針域指向空。每個節點可以存儲任何數據類型。根據類型可以分為單鏈表、雙鏈表、環形鏈表、...

daydream 2019-07-01 10:11 評論0 收藏0