力扣题目学习笔记(OC + Swift)23. 合并 K 个升序链表
2023-12-26 20:51:30
23. 合并 K 个升序链表
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
方法一:顺序合并
记得前面实现过的两个升序链表的合并,我们能否利用之前实现的两个有序链表的合并呢?当然可以,但是性价比不高而已。
时间复杂度:假设每个链表长度为n,当i=0,ans长度为n,i=1时ans长度为2n,因此当i时ans长度为in,求和公式得到O(k+1)k/2n),约等于O(NK^2)
空间复杂度:O(1)
时间复杂度太高了,但是先实现再优化吧…
Swift
//朴素解法,利用之前已经实现的两个有序链表的合并算法
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
let cnt = lists.count
guard cnt > 0 else {return nil}
//合并两个有序链表函数
func mergeTwoListNode(_ list1: ListNode?, _ list2:ListNode?) -> ListNode? {
guard list1 != nil else { return list2 }
guard list2 != nil else { return list1 }
//构造哑巴节点
let dummyNode = ListNode(-1);
var pre:ListNode? = dummyNode;
var list1 = list1
var list2 = list2
while list1 != nil && list2 != nil {
if list1!.value < list2!.value {
pre?.next = list1!;
list1 = list1?.next;
}else {
pre?.next = list2
list2 = list2?.next
}
pre = pre?.next
}
pre?.next = list1 != nil ? list1 : list2
return dummyNode.next
}
var ans:ListNode?
for i in 0..<cnt {
ans = mergeTwoListNode(ans, lists[i])
}
return ans
}
OC
- (ListNodeOC * _Nullable) mergeKLists:(NSArray <ListNodeOC *>*)lists {
if (lists.count <= 0) {
return nil;
}
ListNodeOC *ans = nil;
for (NSInteger i=0; i<lists.count; i++) {
ans = [self mergeTwoList:ans list2:lists[i]];
}
return ans;
}
- (ListNodeOC * _Nullable)mergeTwoList:(ListNodeOC * _Nullable)list list2:(ListNodeOC * _Nullable)list2 {
if (!list || !list2) {
return list ? list : list2;
}
//构造哑巴节点
ListNodeOC *dummyNode = [[ListNodeOC alloc] initWithVal:-1];
ListNodeOC *prev = dummyNode;
while (list && list2) {
if (list.val < list2.val) {
prev.next = list;
list = list.next;
}else {
prev.next = list2;
list2 = list2.next;
}
prev = prev.next;
}
//将任意一个剩余的部分拼接起来
prev.next = list ? list : list2;
return dummyNode.next;
}
方法二、分治法 (推荐)
思路
考虑优化方法一,用分治的方法进行合并。
- 将 k 个链表配对并将同一对中的链表合并;
- 第一轮合并以后, k个链表被合并成了 k/2个链表,平均长度为 2n/k,然后是 k/4个链表, k/8个链表等等;
- 重复这一过程,直到我们得到了最终的有序链表。
时间复杂度:渐进时间复杂度为 O(kn×log?k)
空间复杂度:O(logk)
Swift
//分治合并
func mergeKLists(_ lists: [ListNode?]) -> ListNode? {
func merge(_ lists: [ListNode?], _ left: Int, _ right:Int) -> ListNode? {
if left == right {
return lists[left]
}
if left > right { return nil }
let mid = (left + right) >> 1
//mergeTwoListNode 同方法一中
return mergeTwoListNode(merge(lists, left, mid), merge(lists, mid+1, right))
}
return merge(lists, 0, lists.count-1)
}
OC
- (ListNodeOC * _Nullable) merge:(NSArray <ListNodeOC *>*)lists left:(NSInteger)left right:(NSInteger)right {
if (left == right) {
return lists[left];
}
if (left > right) {
return nil;
}
NSInteger mid = (left+right) / 2;
//mergeTwoList 方法用上面👆🏻
return [self mergeTwoList:[self merge:lists left:left right:mid] list2:[self merge:lists left:mid+1 right:right]];
}
//分治合并
- (ListNodeOC * _Nullable) mergeKLists:(NSArray <ListNodeOC *>*)lists {
return [self merge:lists left:0 right:lists.count-1];
}
文章来源:https://blog.csdn.net/zzl819954692/article/details/135216978
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!