【算法】LeetCode 热题 HOT 100 整理_leetcode hot100

作者：花生_TL007 | 2024-06-07 11:04:55

踩

leetcode hot100

23.合并K个升序链表

在这里插入图片描述
这个题。。你说它是hard吧，我觉得并不没达到，但你说不是hard吧，我自己做还真没AC，一直在超时，用了 优先队列 之后才成功AC，排在88%左右。

所以这个题主要是为了记录一下 优先队列 的这个概念，以及使用方式。

不过首先还是说一下题目思路，一下有几种题解：

每次合并两个链表，对于k个链表，合并k-1次
每次合并两个链表，对于k个链表，合并 $log_2k$ 次
优先队列
这个方法中，优化的重点是这个优先队列，基本思路是对于k个链表的表头，每次对这k个数比大小，取最小的当返回链表的next，然后最小的这个listNode就可以向后错一位了。这个思路我刚看完题就想到了。。奈何没有意识到优先队列竟然这么重要。。。如果每次都是k个数比大小的话，时间复杂度是 $k^2n$ ，因为相当于每生成一个结点都要比大小，比大小就需要k次计算，共有nk个节点，所以复杂度就是 $k^2n$

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/花生_TL007/article/detail/685116