美文网首页算法
《每周一道算法题》（三）合并K个有序链表

《每周一道算法题》（三）合并K个有序链表

作者: 路飞_Luck | 来源:发表于2019-11-17 22:22 被阅读0次
题目描述

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

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6
一 思路一 最笨方法
  • 将所有节点添加到一个数组中
    • 对数组中的节点从小到大进行排序
    • 从数组中从小到大依次取出节点，串成链表

图解

image.png
  • 核心代码如下
- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    // 构造三个链表
    LinkNode *k1 = [[LinkNode alloc] initWithPrev:nil element:@(1) next:nil];
    LinkNode *k2 = [[LinkNode alloc] initWithPrev:k1 element:@(4) next:nil];
    LinkNode *k3 = [[LinkNode alloc] initWithPrev:k2 element:@(7) next:nil];
    
    LinkNode *k4 = [[LinkNode alloc] initWithPrev:nil element:@(2) next:nil];
    LinkNode *k5 = [[LinkNode alloc] initWithPrev:k4 element:@(5) next:nil];
    LinkNode *k6 = [[LinkNode alloc] initWithPrev:k5 element:@(8) next:nil];
    
    LinkNode *k7 = [[LinkNode alloc] initWithPrev:nil element:@(3) next:nil];
    LinkNode *k8 = [[LinkNode alloc] initWithPrev:k7 element:@(6) next:nil];
    LinkNode *k9 = [[LinkNode alloc] initWithPrev:k8 element:@(9) next:nil];
    
    // 方法一
    NSArray *linkNodes = @[k1,k4,k7];
    LinkNode *k = [self mergeManyLists:linkNodes];
    while (k) {
        NSLog(@"%@",[k description]);
        k = k.next;
    }
}

/// 方法一:合并N个有序链表
- (LinkNode *)mergeManyLists:(NSArray *)linkNodes {
    if (!linkNodes || linkNodes.count == 0) {
        return nil;
    }
    NSMutableArray *nodes = [NSMutableArray array];
    for (LinkNode *node in linkNodes) {
        __strong LinkNode *strongNode = node;
        while (strongNode != nil) {
            [nodes addObject:strongNode];
            strongNode = strongNode.next;
        }
    }
    // 排序
    NSArray *newNodes = [nodes sortedArrayUsingComparator:^NSComparisonResult(LinkNode *obj1, LinkNode *obj2) {
        if (obj1.value > obj2.value) {
            return NSOrderedDescending;
        }
        return NSOrderedAscending;
    }];
    LinkNode *head = [[LinkNode alloc] init];
    LinkNode *cur = head;
    for (LinkNode *node in newNodes) {
        cur = cur.next = node;
    }
    return head.next;
}
  • 运行结果
2019-11-12 23:12:02.674864+0800 02_MergeTwoLists[30509:1059927] (null)_1_2
2019-11-12 23:12:02.675147+0800 02_MergeTwoLists[30509:1059927] 1_2_3
2019-11-12 23:12:02.675315+0800 02_MergeTwoLists[30509:1059927] 2_3_4
2019-11-12 23:12:02.675583+0800 02_MergeTwoLists[30509:1059927] 3_4_5
2019-11-12 23:12:02.675706+0800 02_MergeTwoLists[30509:1059927] 4_5_6
2019-11-12 23:12:02.675810+0800 02_MergeTwoLists[30509:1059927] 5_6_7
2019-11-12 23:12:02.675941+0800 02_MergeTwoLists[30509:1059927] 6_7_8
2019-11-12 23:12:02.676053+0800 02_MergeTwoLists[30509:1059927] 7_8_9
2019-11-12 23:12:02.676159+0800 02_MergeTwoLists[30509:1059927] 8_9_null

时间复杂度:O(nlogn)
空间复杂度:O(n)

二 思路二 逐一比较
image.png
  • 核心代码如下
/// 方法二 逐一比较
- (LinkNode *)mergeManyLists2:(NSMutableArray<LinkNode *> *)linkNodes {
    if (linkNodes == nil || linkNodes.count == 0) {
        return nil;
    }
    LinkNode *head = [[LinkNode alloc] init];
    LinkNode *cur = head;
    
    while (true) {
        int minIndex = -1;
        for (int i = 0; i < linkNodes.count; i++) {
            if (linkNodes[i] == nil || linkNodes[i].element == nil) {
                continue;
            }
            
            if (minIndex == -1 || linkNodes[i].value < linkNodes[minIndex].value) {
                minIndex = i;
            }
        }
        if (minIndex  == -1) {
            break;
        }
        
        cur = cur.next = linkNodes[minIndex];
        linkNodes[minIndex] = linkNodes[minIndex].next;
    }
    return head.next;
}
  • 测试代码
- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view, typically from a nib.
    
    LinkNode *nilNode = [[LinkNode alloc] initWithPrev:nil element:nil next:nil];
    
    // 构造三个链表
    LinkNode *k1 = [[LinkNode alloc] initWithPrev:nil element:@(1) next:nil];
    LinkNode *k2 = [[LinkNode alloc] initWithPrev:k1 element:@(4) next:nil];
    LinkNode *k3 = [[LinkNode alloc] initWithPrev:k2 element:@(7) next:nil];
    
    LinkNode *k4 = [[LinkNode alloc] initWithPrev:nil element:@(2) next:nil];
    LinkNode *k5 = [[LinkNode alloc] initWithPrev:k4 element:@(5) next:nil];
    LinkNode *k6 = [[LinkNode alloc] initWithPrev:k5 element:@(8) next:nil];

    LinkNode *k7 = [[LinkNode alloc] initWithPrev:nil element:@(3) next:nil];
    LinkNode *k8 = [[LinkNode alloc] initWithPrev:k7 element:@(6) next:nil];
    LinkNode *k9 = [[LinkNode alloc] initWithPrev:k8 element:@(9) next:nil];
   
    // 为了需要,每个节点最后是一个空的节点
    k3.next = nilNode;
    k6.next = nilNode;
    k9.next = nilNode;
    
    // 方法二 逐一比较
    NSMutableArray *linkNodes = [NSMutableArray arrayWithArray:@[k1,k4,k7]];
    LinkNode *k = [self mergeManyLists2:linkNodes];
    while (k) {
        NSLog(@"%@",[k description]);
        k = k.next;
    }
}
  • 运行结果如下
2019-11-17 10:43:34.914883+0800 02_MergeTwoLists[40077:1519139] (null)_1_2
2019-11-17 10:43:34.915081+0800 02_MergeTwoLists[40077:1519139] 1_2_3
2019-11-17 10:43:34.915177+0800 02_MergeTwoLists[40077:1519139] 2_3_4
2019-11-17 10:43:34.915274+0800 02_MergeTwoLists[40077:1519139] 3_4_5
2019-11-17 10:43:34.915491+0800 02_MergeTwoLists[40077:1519139] 4_5_6
2019-11-17 10:43:34.915623+0800 02_MergeTwoLists[40077:1519139] 5_6_7
2019-11-17 10:43:34.915744+0800 02_MergeTwoLists[40077:1519139] 6_7_8
2019-11-17 10:43:34.915865+0800 02_MergeTwoLists[40077:1519139] 7_8_9
2019-11-17 10:43:34.915981+0800 02_MergeTwoLists[40077:1519139] 8_9_(null)
2019-11-17 10:43:34.916102+0800 02_MergeTwoLists[40077:1519139] 9_(null)_null
三 思路三-逐一两两合并
image.png
  • 核心代码
/// 方法三 逐一两两合并
- (LinkNode *)mergeManyLists3:(NSMutableArray<LinkNode *> *)linkNodes {
    if (linkNodes == nil || linkNodes.count == 0) {
        return nil;
    }
    for (int i = 1; i < linkNodes.count; i++) {
        linkNodes[0] = [self mergeTwoLists:linkNodes[0] k2:linkNodes[i]];
    }
    return linkNodes[0];
}

/// 方法一:递归
/// 1.只要是用到递归,首先要搞清楚一个问题,这个递归函数的功能是什么
/// 2.递归基:边界
- (LinkNode *)mergeTwoLists:(LinkNode *)k1 k2:(LinkNode *)k2 {
    if (k1 == nil) return k2;
    if (k2 == nil) return k1;
    
    if (k1.value <= k2.value) {
        k1.next = [self mergeTwoLists:k1.next k2:k2];
        return k1;
    } else {
        k2.next = [self mergeTwoLists:k1 k2:k2.next];
        return k2;
    }
}
  • 测试代码
/// 方法三 逐一两两合并
NSMutableArray *linkNodes = [NSMutableArray arrayWithArray:@[k1,k4,k7]];
LinkNode *k = [self mergeManyLists3:linkNodes];
while (k) {
    NSLog(@"%@",[k description]);
    k = k.next;
}
  • 运行结果
2019-11-17 11:19:14.687574+0800 02_MergeTwoLists[40935:1548483] null_1_2
2019-11-17 11:19:14.687798+0800 02_MergeTwoLists[40935:1548483] 1_2_3
2019-11-17 11:19:14.687948+0800 02_MergeTwoLists[40935:1548483] 2_3_4
2019-11-17 11:19:14.688098+0800 02_MergeTwoLists[40935:1548483] 3_4_5
2019-11-17 11:19:14.688245+0800 02_MergeTwoLists[40935:1548483] 4_5_6
2019-11-17 11:19:14.688401+0800 02_MergeTwoLists[40935:1548483] 5_6_7
2019-11-17 11:19:14.688515+0800 02_MergeTwoLists[40935:1548483] 6_7_8
2019-11-17 11:19:14.688620+0800 02_MergeTwoLists[40935:1548483] 7_8_9
2019-11-17 11:19:14.688727+0800 02_MergeTwoLists[40935:1548483] 8_9_null
四 思路四-优先级队列（小顶堆）
image.png
五 思路五-分治策略
image.png
  • 核心代码
/// 方法五 - 分治策略
- (LinkNode *)mergeManyLists5:(NSMutableArray<LinkNode *> *)linkNodes {
    if (linkNodes == nil || linkNodes.count == 0) {
        return nil;
    }
    
    int step = 1;
    while (step < linkNodes.count) {
        int nextStep = step << 1;
        for (int i = 0; i + step < linkNodes.count; i += nextStep) {
            linkNodes[i] = [self mergeTwoLists:linkNodes[i] k2:linkNodes[i + step]];
        }
        step = nextStep;
    }
    return linkNodes[0];
}
  • 运行结果
2019-11-17 21:57:36.968482+0800 02_MergeTwoLists[54576:1953555] null_1_2
2019-11-17 21:57:36.968663+0800 02_MergeTwoLists[54576:1953555] 1_2_3
2019-11-17 21:57:36.968778+0800 02_MergeTwoLists[54576:1953555] 2_3_4
2019-11-17 21:57:36.968890+0800 02_MergeTwoLists[54576:1953555] 3_4_5
2019-11-17 21:57:36.969008+0800 02_MergeTwoLists[54576:1953555] 4_5_6
2019-11-17 21:57:36.969148+0800 02_MergeTwoLists[54576:1953555] 5_6_7
2019-11-17 21:57:36.969267+0800 02_MergeTwoLists[54576:1953555] 6_7_8
2019-11-17 21:57:36.969376+0800 02_MergeTwoLists[54576:1953555] 7_8_9
2019-11-17 21:57:36.969485+0800 02_MergeTwoLists[54576:1953555] 8_9_null

本文参考MJ老师的每日一道算法题

项目链接地址 - 03_MergeManyLists

每周一道算法题 - 笔记

相关文章

  • LeetCode-23-合并K个有序链表

    LeetCode-23-合并K个有序链表 题目 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂...

  • LeetCode 专题 ：分治算法

    LeetCode 第 23 题：归并多个有序链表 传送门：23. 合并K个排序链表。 合并 k 个排序链表，返回合...

  • 《每周一道算法题》（三）合并K个有序链表

    题目描述 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 一 思路一 最笨方法 将...

  • 链表操作

    合并2个有序链表 合并k个有序链表 这俩题挺好的，既考察了合并，又考察了递归与分治。 删除倒数第k个节点 思路到没...

  • 图解堆排序，拾遗

    这篇文章我们一起来复习一下堆排序，同时做一道经典的堆排序算法题：合并k个有序链表[https://leetcode...

  • 合并K个排序链表

    合并K个排序链表 题目描述 基本思路 这道题属于双链表合并的进阶。理解这道题首先需要了解有序双链表合并的解法。 已...

  • 23. 合并K个排序链表

    自己解法 合并K个有序列表，和21题合并两个有序链表思路类似，这个题最开始想偏了，想比较每个链表的头结点，然后后移...

  • iOS算法题（三）合并K个有序链表

    题目描述 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 一 思路一 最笨方法 将...

  • leecode刷题（27）-- 合并k个排序链表

    leecode刷题（27）-- 合并k个排序链表 合并k个排序链表 合并 k 个排序链表，返回合并后的排序链表。请...

  • Python小白 Leetcode刷题历程 No.21-N

    Python小白 Leetcode刷题历程 No.21-No.25 合并两个有序链表、括号生成、合并K...

网友评论

    本文标题：《每周一道算法题》（三）合并K个有序链表

    本文链接：https://www.haomeiwen.com/subject/jehcictx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    算法

    关于我们|服务条款|联系我们|《每周一道算法题》（三）合并K个有序链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！