摘要:题目合并排序链表并返回一个排序列表。分析和描述它的复杂性。直接对个链表合并,找到个链表头最小的,将值追加到放在新创建的链表中,并把头移到下一个节点,直到所有的链表头运行后发现超时尝试两两合并两个链表,知道最终合并成一个运行通过
题目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并k排序链表并返回一个排序列表。分析和描述它的复杂性。
直接对k个链表合并,找到k个链表头最小的,将值追加到放在新创建的链表中,并把头移到下一个节点,直到所有的链表头none
# Definition for singly-linked list. class ListNode(object): def __init__(self, x): self.val = x self.next = None class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ head = None walk_list = [lists[i] for i in range(len(lists))] pre = None while len(filter(lambda x: x is not None, walk_list)): for i in range(len(walk_list)): if walk_list[i] is not None: min_val = walk_list[i].val min_index = i break for i in range(len(walk_list)): if walk_list[i] and walk_list[i].val < min_val: min_val = walk_list[i].val min_index = i l = ListNode(min_val) walk_list[min_index] = walk_list[min_index].next if head is None: head = l pre = head else: pre.next = l pre = l return head
运行后发现超时
尝试两两合并两个链表,知道最终合并成一个
class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None i = 0 j = len(lists) - 1 r_list = lists while i < j: l = [] while i < j: node = self.mergetwolists(r_list[i], r_list[j]) l.append(node) i += 1 j -= 1 if i == j: l.append(r_list[i]) r_list = l i = 0 j = len(r_list) - 1 return r_list[0] def mergetwolists(self, l1, l2): if l1 == None: return l2 if l2 == None: return l1 l1_head = l1 l2_head = l2 head = None pre = None while l1_head and l2_head: if l1_head.val < l2_head.val: l = ListNode(l1_head.val) l1_head = l1_head.next else: l = ListNode(l2_head.val) l2_head = l2_head.next if pre == None: pre = l head = l else: pre.next = l pre = l if l1_head is None: pre.next = l2_head if l2_head is None: pre.next = l1_head return head
运行通过
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/40724.html
摘要:思路这题中的中,个还有其中个别的等于的情况,所以要判断一下再加入代码 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Heap Time Complexity: Update the heap costs O(nklogk) Space ...
摘要:的想法就是用每次得到最小的链表头的值,输出。每个都有一个关注人列表,用储存。用户可以发消息,关注别人,取消关注别人。可以系统得到关注人的消息合集,这个方法必须在这个层级。因为用户只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...
摘要:分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解,子问题之间没有相关性,这一点是分治算法跟动态规划的明显区别。 Time:2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 题目:Merge K...
摘要:注意因为堆中是链表节点,我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见:https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...
摘要:分治做法中,函数依然是将链表结点两两进行比较,然后在函数中迭代两个二分后的结果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...
阅读 3710·2021-11-25 09:43
阅读 2160·2021-11-23 10:13
阅读 791·2021-11-16 11:44
阅读 2326·2019-08-29 17:24
阅读 1346·2019-08-29 17:17
阅读 3456·2019-08-29 11:30
阅读 2539·2019-08-26 13:23
阅读 2318·2019-08-26 12:10