【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表

简介: 【❤️算法笔记❤️】-每日一刷-23、合并 K 个升序链表

题目

给你一个链表数组,每个链表都已经按升序排列

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2:

输入:lists = []
输出:[]

示例 3:

输入:lists = [[]]
输出:[]

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4

通过次数

766.6K

提交次数

1.3M

通过率

59.1%

思路

  • 优先队列
  • Lambda表达式
  • 最小堆、最大堆

解答

//给你一个链表数组,每个链表都已经按升序排列。 
//
// 请你将所有链表合并到一个升序链表中,返回合并后的链表。 
//
// 
//
// 示例 1: 
//
// 输入:lists = [[1,4,5],[1,3,4],[2,6]]
//输出:[1,1,2,3,4,4,5,6]
//解释:链表数组如下:
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
// 
//
// 示例 2: 
//
// 输入:lists = []
//输出:[]
// 
//
// 示例 3: 
//
// 输入:lists = [[]]
//输出:[]
// 
//
// 
//
// 提示: 
//
// 
// k == lists.length 
// 0 <= k <= 10^4 
// 0 <= lists[i].length <= 500 
// -10^4 <= lists[i][j] <= 10^4 
// lists[i] 按 升序 排列 
// lists[i].length 的总和不超过 10^4 
// 
//
// Related Topics 链表 分治 堆(优先队列) 归并排序 👍 2772 👎 0
//leetcode submit region begin(Prohibit modification and deletion)
import java.util.List;
import java.util.PriorityQueue;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0) return null;
        //虚拟头节点
        ListNode dummy=new ListNode();
        ListNode p=dummy;
        //优先级队列--最小堆
        PriorityQueue<ListNode> pq=new PriorityQueue<ListNode>(
                lists.length,(a,b)->(a.val-b.val)
        );
        //将k个链表的头节点加入最小堆
        for (ListNode head :lists) {
            if (head != null)
                pq.add(head);
        }
            while (!pq.isEmpty()) {
                //获取最小节点,接到结果链表中
                ListNode node = pq.poll();
                p.next = node;
                if (node.next != null) {
                    pq.add(node.next);
                }
                p = p.next;
            }
        return dummy.next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)


目录
相关文章
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
2月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
|
2月前
|
算法
经典算法之链表篇(二)
经典算法之链表篇(二)
|
2月前
|
算法 索引
经典算法之链表篇
经典算法之链表篇
|
2月前
|
算法 API 计算机视觉
人脸识别笔记(一):通过yuface调包(参数量54K更快更小更准的算法) 来实现人脸识别
本文介绍了YuNet系列人脸检测算法的优化和使用,包括YuNet-s和YuNet-n,以及通过yuface库和onnx在不同场景下实现人脸检测的方法。
66 1
|
2月前
|
JSON 算法 数据可视化
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
这篇文章是关于如何通过算法接口返回的目标检测结果来计算性能指标的笔记。它涵盖了任务描述、指标分析(包括TP、FP、FN、TN、精准率和召回率),接口处理,数据集处理,以及如何使用实用工具进行文件操作和数据可视化。文章还提供了一些Python代码示例,用于处理图像文件、转换数据格式以及计算目标检测的性能指标。
71 0
测试专项笔记(一): 通过算法能力接口返回的检测结果完成相关指标的计算(目标检测)
|
2月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
18 0
|
2月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
33 0
|
9天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。