数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时装学
法律学在 Python 中合并 k 个有序的列表
假设我们有一些列表，这些列表是经过排序的。我们必须将这些列表合并成一个列表。为了解决这一问题，我们将使用堆数据结构。因此，如果列表为 [1,4,5], [1,3,4], [2,6], 则最终列表将为 [1,1,2,3,4,4,5,6]。
为了解决这一问题，我们将按照以下步骤进行 −
创建一个堆
对于 lists 中的每个链表 l −
如果 l 不为 0，则将 l 插入堆中
res := null 并且 res_next := null
进行一个无限循环 −
temp := 堆中的最小值
如果堆中没有元素，则返回 res
如果 res 为 0，则
res := temp, res_next := temp
temp := temp 的下一个元素
如果 temp 不为 0，则将 temp 插入堆中
res 的下一个为 null
否则 −
res_next 的下一个为 temp, temp := temp 的下一个, res_next := res_next 的下一个
如果 temp 不为 null，则将 temp 插入堆中
res_next 的下一个为 null
示例
让我们看以下实现以获得更好的理解 −
class ListNode:
def __init__(self, data, next = None):
self.val = data
self.next = next
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Heap:
def __init__(self):
self.arr = []
def print_heap(self):
res = " "
for i in self.arr:
res += str(i.val) + " "
print(res)
def getVal(self,i):
return self.arr[i].val
def parent(self,i):
return (i-1)//2
def left(self,i):
return (2*i + 1)
def right(self,i):
return (2*i + 2)
def insert(self,value):
self.arr.append(value)
n = len(self.arr)-1
i = n
while i != 0 and
self.arr[i].val<self.arr[self.parent(i)].val:
self.arr[i],self.arr[self.parent(i)] = self.arr[self.parent(i)],self.arr[i]
i = self.parent(i)
def heapify(self,i):
left = self.left(i)
right = self.right(i)
smallest = i
n= len(self.arr)
if left<n and self.getVal(left)<self.getVal(smallest): smallest = left
if right <n and self.getVal(right)<self.getVal(smallest): smallest = right
if smallest!=i:
self.arr[i],self.arr[smallest] = self.arr[smallest],self.arr[i]
self.heapify(smallest)
def extractMin(self):
n = len(self.arr)
if n==0:
return '#'
if n== 1:
temp =self.arr[0]
self.arr.pop()
return temp
root = self.arr[0]
self.arr[0] = self.arr[-1]
self.arr.pop()
self.heapify(0)
return root
class Solution(object):
def mergeKLists(self, lists):
heap = Heap()
for i in lists:
if i:
heap.insert(i)
res = None
res_next = None
while True:
temp = heap.extractMin()
if temp == "#":
return res
if not res:
res = temp
res_next = temp
temp = temp.next
if temp:
heap.insert(temp)
res.next = None
else:
res_next.next = temp
temp = temp.next
res_next=res_next.next
if temp:
heap.insert(temp)
res_next.next = None
ob = Solution()
lists = [[1,4,5],[1,3,4],[2,6]]
lls = []
for ll in lists:
l = make_list(ll)
lls.append(l)
print_list(ob.mergeKLists(lls))输入
[[1,4,5],[1,3,4],[2,6]]
输出
[1, 1, 2, 3, 4, 4, 5, 6, ]
更新时间: 2020-05-26
790 次观看
广告