23. Merge k Sorted Lists

qingshanli1988 發布于2019-07-30 14:28 / 2393人閱讀

摘要：題目合并排序鏈表并返回一個排序列表。分析和描述它的復雜性。直接對個鏈表合并，找到個鏈表頭最小的，將值追加到放在新創建的鏈表中，并把頭移到下一個節點，直到所有的鏈表頭運行后發現超時嘗試兩兩合并兩個鏈表，知道最終合并成一個運行通過

題目

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

運行通過

GPU云服務器云服務器 Lists Sorted sorted-array sorted_set

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/40724.html

[LeetCode] 23. Merge k Sorted Lists

摘要：思路這題中的中，個還有其中個別的等于的情況，所以要判斷一下再加入代碼 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 ...

Codeing_ls 2019-08-15 12:25 評論0 收藏0
355. Design Twitter , 用23. Merge k Sorted Lists和OO

摘要：的想法就是用每次得到最小的鏈表頭的值，輸出。每個都有一個關注人列表，用儲存。用戶可以發消息，關注別人，取消關注別人?？梢韵到y得到關注人的消息合集，這個方法必須在這個層級。因為用戶只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...

1fe1se 2019-08-14 18:00 評論0 收藏0
LeetCode 之 JavaScript 解答第23題 —— 合并K個有序鏈表（Merge K S

摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關聯原問題分解成的子問題可以獨立求解，子問題之間沒有相關性，這一點是分治算法跟動態規劃的明顯區別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿題目：Merge K...

zhou_you 2019-08-23 16:53 評論0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因為堆中是鏈表節點，我們在初始化堆時還要新建一個的類。代碼初始化大小為的堆拿出堆頂元素將堆頂元素的下一個加入堆中 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...

stefanieliang 2019-08-14 12:30 評論0 收藏0
[LintCode] Merge K Sorted Lists [DC/Heap]

摘要：分治做法中，函數依然是將鏈表結點兩兩進行比較，然后在函數中迭代兩個二分后的結果。 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, ...

happyhuangjinjin 2019-08-14 15:32 評論0 收藏0