[leetcode-排序]--23. Merge k Sorted Lists

2024-05-23 18:18

本文主要是介绍[leetcode-排序]--23. Merge k Sorted Lists,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Question 23. Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

中文:合并k个有序的链表,然后返回一个有序的链表的表头结点。

解决思路:

1) 模仿两个链表的做法:

用一个链表数组ListNode[] ps 来保存每个链表的索引,然后每次比较的时候,就是找出 ps数组 中的最小值,其余思想和Question21 基本一样,这个时候的缺点就是:每次找最小值都用进行一次遍历ps数组,时间复杂度是O(k), 这样整体的时间开销就比较大了。

这种思路我就不给出代码了,和Question21一样的套路,唯一就是需要一个另外的函数来计算 ps 数组的最小值。

2)使用Java中的PriorityQueue解决

先看看PriorityQueue的构造函数:

public PriorityQueue(int initialCapacity, Comparator<? super E> comparator)

使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器对元素进行排序。

里面的有序性就是由PriorityQueue维护的:

/*** 这是由Java的PriorityQueue来维护有序性.* @param lists 链表头结点数组* @return*/
public static ListNode mergeKLists(ListNode[] lists) {if (lists==null || lists.length==0)return null;//队列中的元素是按照从小到大排序的PriorityQueue<ListNode> queue= new PriorityQueue<ListNode>(lists.length, new Comparator<ListNode>(){@Overridepublic int compare(ListNode o1,ListNode o2){if (o1.val<o2.val)return -1;else if (o1.val==o2.val)return 0;elsereturn 1;}});//头结点ListNode dummy = new ListNode(0);ListNode tail=dummy;//将每个链表的头结点放入队列for (ListNode node:lists)if (node!=null)queue.add(node);while (!queue.isEmpty()){tail.next=queue.poll();//获取并移除此队列的头,如果此队列为空,则返回 null。tail=tail.next;if (tail.next!=null)queue.add(tail.next);}return dummy.next;
}

这篇关于[leetcode-排序]--23. Merge k Sorted Lists的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/996337

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

安卓链接正常显示,ios#符被转义%23导致链接访问404

原因分析: url中含有特殊字符 中文未编码 都有可能导致URL转换失败,所以需要对url编码处理  如下: guard let allowUrl = webUrl.addingPercentEncoding(withAllowedCharacters: .urlQueryAllowed) else {return} 后面发现当url中有#号时,会被误伤转义为%23,导致链接无法访问

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点