problem LeetCode 上的表述如下:
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
我能够通过 131 个测试案例中的 129 个,但在案例 130 上遇到了“超出时间限制”。下面是我的实现。
有人能找出瓶颈吗?有什么改进时间复杂度的建议吗?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# def print_lists(self, lists):
# idx = 0
# while idx < len(lists):
# ptr = lists[idx]
# _l = []
# while ptr is not None:
# _l.append(ptr.val)
# ptr = ptr.next
# idx += 1
# print(_l)
def min_idx(self, lists):
idx = 0
for i in range(len(lists)):
if lists[i] is None:
continue
elif lists[idx] is None:
idx = i
elif lists[i].val < lists[idx].val:
idx = i
return idx
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
head = tail = ListNode(-1)
while len(lists) > 0:
m_idx = self.min_idx(lists)
if lists[m_idx] is None:
return head.next
tail.next = lists[m_idx]
tail = tail.next
lists[m_idx] = lists[m_idx].next
if lists[m_idx] is None:
del lists[m_idx]
return head.next
我在没有使用 del
的情况下遇到了“超出时间限制”的问题。测试用例 130 包含 10,000 个链表。
最佳答案
这是一个更简单、更快速的代码版本,它避免了多个 if:
def min_idx(self, lists):
idx = 0
for i in range(len(lists)):
if lists[i].val < lists[idx].val:
idx = i
return idx
def mergeKLists(self, lists):
head = tail = ListNode(-1)
lists = list(filter(lambda x: x is not None, lists))
while len(lists) > 0:
m_idx = self.min_idx(lists)
tail.next = lists[m_idx]
tail = tail.next
lists[m_idx] = lists[m_idx].next
if lists[m_idx] is None:
del lists[m_idx]
return head.next
为了更好的时间,您需要将实现更改为:
- 使用堆将 min_idx 操作减少到 O(log k) 而不是 O(k) 是 k 个列表的数量
- 只需将所有内容放入一个数组,对其进行排序,然后将其放回 ListNode
- 在 O(最长列表的长度)中合并 2 个列表,并递归地成对合并,直到剩下 1 个
关于python - 力扣 : Problem 23 - Merge K Sorted Lists,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56028554/