【算法解析LeetCode by Javascript】23. 合并K個排序鏈表

icattlecoder 發(fā)布于2019-08-26 13:37 / 1472人閱讀

摘要：合并個排序鏈表合并個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。那么總的復雜度就是提交

合并K個排序鏈表

合并 k 個排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復雜度。

示例:

輸入:
[
  1->4->5,
  1->3->4,
  2->6
]
輸出: 1->1->2->3->4->4->5->6

1.暴力破解法

此解法過于暴力，請謹慎使用

原理就是把所有的節(jié)點拆解，排序，再從新組合成一個列表，道理容易理解

時間復雜度為 O(nlogn)

2.枚舉法

此解法的主要思路為遍歷所有列表的頭部值，把最小的一個推入到當前結果隊列里

具體解法為

var isOver = function (lists) {
    let r = true
    lists.map(val => {
        if (val) {
            r = false
            return r
        }
    })
    
    return r
}

var minNode = function (lists) {
    let val = null
    let j
    for (var i = 0; i < lists.length; i++) {
        if (lists[i]) {
            if (val === null) {
                val = lists[i].val
            }
            // console.log(lists[i].val, val)
            if (lists[i].val <= val) {
                val = lists[i].val
                j = i
            }
        }
    }
    console.log(j)
    let m = new ListNode(lists[j].val)
    lists[j] = lists[j].next
    
    return m
}

var mergeKLists = function(lists) {
    if (lists.length === 0) return ""
    let result = null
    while (!isOver(lists)) {
        if (!result) {
            result = minNode(lists)
        } else {
            let z = result
            while (z.next) {
              z = z.next
            }
            z.next = minNode(lists)
        }
    }
    
    return result
    
};

最極端的情況下我們每次獲取元素都需要遍歷k個鏈表，那么復雜度就是O(kn),k值復雜度越高。不一定比方法-更快

3.分治法

我們只需要把相鄰列表進行合并，這樣的話我們只需要進行l(wèi)ogN次操作就可以把列表歸并成一個有序列表

遞歸深度一共是logk，每一層的遞歸操作次數(shù)都是n次，n是所有元素的個數(shù)。那么總的復雜度就是
O(nlogk)

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function(lists) {
    if(lists.length == 0) return null;
    var k = lists.length;
    while(k > 1){
        for (let i = 0; i < ~~(k / 2); i++) {
            lists[i] = mergeTwoLists(lists[i], lists[i + ~~((k + 1) / 2)]);
        }
        k = ~~((k + 1) / 2);
    }
    return lists[0];
};
var mergeTwoLists = function (l1, l2) {
    if (l1 == null) return l2
    if (l2 == null) return l1
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    } else {
        l2.next = mergeTwoLists(l1, l2.next)
        return l2
    }
}

提交

GPU云服務器云服務器鏈表排序算法鏈表排序合并鏈表的c語言快速排序算法

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

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

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

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關聯(lián)原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態(tài)規(guī)劃的明顯區(qū)別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿題目：Merge K...

zhou_you 2019-08-23 16:53 評論0 收藏0
6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態(tài)碼詳解無狀態(tài)協(xié)議和請求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統(tǒng)設計工程在線診斷系統(tǒng)設計與實現(xiàn)索引背后的數(shù)據(jù)結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0
優(yōu)秀程序員都應該學習的 GitHub 上開源的數(shù)據(jù)結構與算法項目

摘要：強烈推薦上值得前端學習的數(shù)據(jù)結構與算法項目，包含圖的演示過程與視頻講解。該倉庫包含了多種基于的算法與數(shù)據(jù)結構，提供進一步閱讀的解釋和鏈接。數(shù)據(jù)結構和算法必知必會的個代碼實現(xiàn)。 showImg(https://segmentfault.com/img/bVbvpYZ); 前言算法為王。想學好前端，先練好內功，內功不行，就算招式練的再花哨，終究成不了高手；只有內功深厚者，前端之路才會走得...

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

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

dinfer 2019-06-26 18:55 評論0 收藏0