二分查找变形和合并k个有序链表
二分查找变形和合并k个有序链表
leetcode_21 合并2个有序链表
思路一：我们可以通过类似于归并排序合并两个有序集合来做
让pnode1,pnode2分别指向两个链表 list1,list3=2 用pnewHead记录新链表的头，pcur始终用来追踪合并后新链表
的当前位置，不断来迭代追踪，让pcur.next 指向里面的较小者，pcur跟过去，指向当前合并后脸部的最新位置，然后
pnode=pnode.next等 直至pnode1 和 pnode2不满足都有元素了，此时让pcur.next挂上还没完的链表，然后返回新
的合并后的链表头：pnewHead
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if not list1:
return list2
if not list2:
return list1
pnode1, pnode2 = list1, list2
pnewhead, pcur = None, None
if pnode1.val < pnode2.val:
pnewhead = pnode1
pcur = pnode1
pnode1 = pnode1.next
else:
pnewhead = pnode2
pcur = pnode2
pnode2 = pnode2.next
while pnode1 and pnode2:
if pnode1.val < pnode2.val:
pcur.next = pnode1
pcur = pnode1
pnode1 = pnode1.next
else:
pcur.next = pnode2
pcur = pnode2
pnode2 = pnode2.next
if not pnode2 and pnode1:
pcur.next = pnode1
if not pnode1 and pnode2:
pcur.next = pnode2
return pnewhead
思路二的话我们可以通过递归的写法 因为这道题的本质重复的就是比较两个链表的大小，得到较小者，挂到合并后新链表的后面
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeTwoLists(self, list1, list2):
"""
:type list1: Optional[ListNode]
:type list2: Optional[ListNode]
:rtype: Optional[ListNode]
"""
if not list1:
return list2
if not list2:
return list1
pnewhead = None
if list1.val < list2.val:
pnewhead = list1
pnewhead.next = self.mergeTwoLists(list1.next, list2)
else:
pnewhead = list2
pnewhead.next = self.mergeTwoLists(list2.next, list1)
return pnewhead
leetcode_23 合并k个升序链表
思路：# 其实这道题本质上就是让你写个归并排序，这不都你写过的吗，分治的思想你忘了
# 合并k个链表。我们可以用分治的思想，先分治，让有序链表两两合并，最后不断合并，通过局部有序，最后保证全局有序合
# 并
# 当数组链表的被分的只剩下一个链表,及left==right时，这就是base case直接返回lists[left],
# 然后我们取中间位置，继续一份为二的划分，整体类似于树的后续遍历，先左后右最后返回合并后的链表
# 对于两个链表的合并就是我们之前两个链表的合并的代码
# 通过分而治之 最后实现k个链表的合并，本质和归并排序一样，就是分而治之的思想
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if not lists:
return
def mergeKListsCore(lists, left, right):
if left == right:
return lists[left]
mid = left + ((right - left) >> 1)
list1 = mergeKListsCore(lists, left, mid)
list2 = mergeKListsCore(lists, mid + 1, right)
return mergeTwoList(list1, list2)
def mergeTwoList(list1, list2):
if not list1:
return list2
if not list2:
return list1
pnewhead = None
if list1.val < list2.val:
pnewhead = list1
pnewhead.next = mergeTwoList(list1.next, list2)
else:
pnewhead = list2
pnewhead.next = mergeTwoList(list1, list2.next)
return pnewhead
return mergeKListsCore(lists, 0, len(lists) - 1)
leetcode_33 二分查找的变形题目
如何在从k位置逆序后的数组 局部有序的序列中找我们的target
思路：
# 这道题的思路 这道题的话是二分查找的变形 如果进行部分逆序后 那整个序列的话就是一个局部有序的状态
# 我们可以依然用二分查找来做 这样的时间复杂度也是：log(n)
# 首先：我们需要比较mid元素和low元素的大小，如果nums[mid] < nums[low] 说明mid元素处于右边有
# 序部分，否则说明mid元素在左边有效部分
# 在判断mid元素的基础上，我们需要判断target元素是处于左边有序部分还是右边有序部分
# 如果nums[mid] < nums[low]： 并且，nums[mid]<=target<=nums[hign] 说明target在右边有序
# 部分，left = mid+1 否则，right = mid-1
# 如果nums[mid] >= nums[low]:并且nums[left]<=target<=nums[mid] 说明target在左边部分，right=mid-1否则：left=mid+1
# 如果target == nums[mid] return mid
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
if not nums:
return -1
left, right = 0, len(nums) - 1
while left < right:
mid = left + ((right - left) // 2)
if nums[mid] == target:
return mid
if nums[mid] < nums[left]:
if nums[mid] <= target <= nums[right]:
left = mid + 1
else:
right = mid - 1
else:
if nums[left] <= target <= nums[mid]:
right = mid - 1
else:
left = mid + 1
return left if nums[left] == target else -1
END THANKS!