成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

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

icattlecoder / 1534人閱讀

摘要：合并個(gè)排序鏈表合并個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。那么總的復(fù)雜度就是提交

合并K個(gè)排序鏈表

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:

輸入:
[
  1->4->5,
  1->3->4,
  2->6
]
輸出: 1->1->2->3->4->4->5->6
1.暴力破解法

此解法過(guò)于暴力，請(qǐng)謹(jǐn)慎使用

原理就是把所有的節(jié)點(diǎn)拆解，排序，再?gòu)男陆M合成一個(gè)列表，道理容易理解

時(shí)間復(fù)雜度為 O(nlogn)
2.枚舉法

此解法的主要思路為遍歷所有列表的頭部值，把最小的一個(gè)推入到當(dāng)前結(jié)果隊(duì)列里

具體解法為

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個(gè)鏈表，那么復(fù)雜度就是O(kn),k值復(fù)雜度越高。不一定比方法-更快
3.分治法

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

遞歸深度一共是logk，每一層的遞歸操作次數(shù)都是n次，n是所有元素的個(gè)數(shù)。那么總的復(fù)雜度就是
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
    }
}
提交

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/109199.html

相關(guān)文章

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

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

    zhou_you 評(píng)論0 收藏0

  • 6-9月技術(shù)文章匯總

    摘要：分布式的管理和當(dāng)我在談?wù)摷軜?gòu)時(shí)我在談啥狀態(tài)碼詳解無(wú)狀態(tài)協(xié)議和請(qǐng)求支持哪些方法分層協(xié)議棧有哪些數(shù)據(jù)結(jié)構(gòu)運(yùn)用場(chǎng)景說(shuō)說(shuō)你常用的命令為什么要有包裝類(lèi)面向?qū)ο蟮奶卣魇巧妒巧队惺裁春锰幭到y(tǒng)設(shè)計(jì)工程在線(xiàn)診斷系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理軟技能 HTTP 【HTTP】分布式session的管理 【HTTP】Cookie和Session 【HTTP】當(dāng)我在談?wù)揜estFul架構(gòu)時(shí)我在談啥？...

    miya 評(píng)論0 收藏0

  • 優(yōu)秀程序員都應(yīng)該學(xué)習(xí)的 GitHub 上開(kāi)源的數(shù)據(jù)結(jié)構(gòu)與算法項(xiàng)目

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

    cheukyin 評(píng)論0 收藏0

  • 第7期 Datawhale 組隊(duì)學(xué)習(xí)計(jì)劃

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

    dinfer 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<