专栏首页考拉阅读前端团队【算法解析LeetCode by Javascript】23. 合并K个排序链表

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

合并K个排序链表


合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

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

1.暴力破解法

此解法过于暴力,请谨慎使用

原理就是把所有的节点拆解,排序,再从新组合成一个列表,道理容易理解

时间复杂度为 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.分治法

我们只需要把相邻列表进行合并,这样的话我们只需要进行logN次操作就可以把列表归并成一个有序列表

递归深度一共是logk,每一层的递归操作次数都是n次,n是所有元素的个数。那么总的复杂度就是 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
    }
}

提交

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 记录一次开发微信网页分享

    最近在做一个项目需求,分享领好书活动,获取用户的个人信息以及unionID,并诱导用户分享给好友或朋友圈,达到裂变拉新的目的。在做的过程中遇到了一些坑的地方,所...

    super.x
  • vue + 微信二次分享/自定义分享

    如上图,如果不做相关处理,页面进行二次分享,用户看到的就是链接+空图,上面显示的文案(考拉阅读)实际上是获取的title标签中的文案,我在网上查的相关例子有说明...

    super.x
  • vue + 微信获取用户信息

    本次项目做到一个点赞功能,即分享出去一个页面给微信好友,微信好友点开并点赞,需要将点赞用户的微信昵称,微信头像以及微信openid,微信unionid(这个需要...

    super.x
  • Silverlight初级教程-概述

    Silverlight初级教程 概述 Silverlight 是微软的一项新技术,正如之前的asp一样,微软为了保持其竞争力重新设计了他的框架推...

    用户1172164
  • 互联网+物联网:中国统计学的风口

    论坛君:作为一名统计学教员(王汉生教授谦虚了),每天绞尽脑汁做完研究,难得空闲的时候,教授就琢磨琢磨中国统计学的风口在哪里(果然是高大上的问题)。他认为:统计学...

    小莹莹
  • Scala JDBC 查询和更新MySQL

    大数据工程师-公子
  • 网页实现批量数据导入功能

    蛋未明
  • 疫情期间,你们都在囤什么?用一面数据的YiTrackers看电商行业趋势

    中国的电商市场是一个充满活力,或者说充斥着各种变数的商业环境。有时候一些黑天鹅事件,如新冠肺炎,会把整个市场搅得天翻地覆。这个时候,你可能会好奇市场的变化到底是...

    用户1569917
  • 【数据挖掘】rattle:数据挖掘的界面化操作

    R语言是一个自由、免费、源代码开放的软件,它是一个用于统计计算和统计制图的优秀工具。这里的统计计算可以是数据分析、建模或是数据挖掘等,通过无数大牛提供的软件包,...

    小莹莹
  • 贵阳数博会展馆 4万平方米展区千家企业N多新奇

    大数据文摘

扫码关注云+社区

领取腾讯云代金券