题023.合并K个升序链表
题意
给一个链表数组,其中每个链表都已经按照升序排列,将所有链表合并到一个链表中并返回。
eg.
输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
解题
我的解法
本题类似昨天的21题,合并两个升序链表,区别只是链表的数量。所以我第一反应是用类似昨天两两比对的方式,尝试解题,具体的做法是:
- 将所有链表的第一项拿出来比对,找到节点值最小的那一项,接到新链表尾部
- 直到链表数组中只有一条非空链表,遍历结束并将其接到新链表的尾部,输出答案
按照这个思路解题并提交后,发现特别费时,分析下来,时间复杂度是O(mn),m为链表数量,n为链表平均长度。
归并解法
这样的方法效率比较低,参考题解后学习了归并的方法,思路比较简单,每次合并两条链表,直至最后合成一条。
换句话说,可理解为从上而下的合并任务拆分,需要定义一个类似于21题中合并两个链表的函数。
定义一个合并两个链表的函数
def mergeTwoLists(l1:ListNode,l2:ListNode):
a=b=ListNode(None)
while l1 and l2:
if l1.val<l2.val:
b.next=l1
l1=l1.next
else:
b.next=l2
l2=l2.next
b=b.next
if l1:
b.next=l1
if l2:
b.next=l2
return a.next
代码
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
n=len(lists)
if n==0:
return None
elif n==1:
return lists[0]
m=n//2
#利用归并思想,从中间一分为二
return mergeTwoLists(self.mergeKLists(lists[:m]),self.mergeKLists[:m])
最小堆
可以利用python自带的heapq将所有元素构建最小堆,思路比较简单:
- 将所有链表节点的值全部存储到最小堆中
- 对最小堆进行pop操作,每取出一个值就加到新链表后,直至所有元素取出
if not lists:
return None
import heapq
heap=[]
for node in lists:
while node:
heapq.heappush(heap,node.val)
node=node.next
a=b=ListNode(None)
while heap:
b.next=ListNode(heappop(heap))
b=b.next
return a.next
暴力求解
看到一种解法,暴力求解,将所有链表节点放到一个list中,然后依据节点值进行排序,最后把每个节点接到上个节点后
#合并后排序(暴力求解)
helper=[]
for li in lists:
while li:
helper.append(li)
li=li.next
helper=sorted(helper,key=lambda x:x.val)
if not helper:
return None
for i in range(len(helper)-1):
helper[i].next=helper[i+1]
return helper[0]
题026.删除排序数组中重复项
题意
给定一个排序数组,在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
要求: 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
解题
思路:遍历数组,每次把新出现的数塞到第n个位置,输出n+1,主要代码如下:
n=0 #第一个数作为比较值
for i in range(1,len(nums)):
if nums[i]!=nums[n]:
n+=1
nums[n]=nums[i]#更新比较值
return n+1
题033.搜索旋转排序数组
题意
升序排列的整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。
请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。
解题
用二分法 把数组一分为二,取 头、中、尾三个数 进行比较,
- 如果left<=mid,说明左边是升序的,进而判断target是否在这个区间,
- 若在这个区间,将right值设为mid-1
- 若不在,left设为mid+1
- 否则右边是升序的,判断target是否在这个区间
- 若在,left设为mid+1
- 不在,rigt设为mid-1
代码
if not nums:
return -1
left=0
right=len(nums)-1
while left<=right:
mid=(left+right)//2
if nums[mid]==target:
return mid
if nums[left]<=nums[mid]:
if nums[left]<=target<nums[mid]:
right=mid-1
else:
left=mid+1
else:
if nums[mid]<target<=nums[right]:
left=mid+1
else:
right=mid-1
return -1