vlambda博客
学习文章列表

二分查找变形和合并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!