LeetCode-4.寻找两个正序数组的中位数（hard）——折半查找

题目：寻找两个正序数组的中位数

 

思路：

同类题：找到有序数组中第k小的数字——折半查找（删除）

• 计算k值——对于双数组总长度是奇数，则k为双数组长度(len//2 + 1)（向上取整）；若是偶数，则取第len//2、第len//2 + 1两个位置数字的平均数；
• 对已知k的数组进行折半删除： 将两个数组分为数组A和数组B。分别找到A[k/2]和B[k/2]。此时，可能有2种情况：
  • 两边数组长度都足够用：pass
  • 若有一边数组长度不够用，则直接将数组的角标移动到该数组最末位，并记录新的值，因为这个值对应的就是后面即将删除掉的数字的个数。
  • 若有某个数组长度是0，那么可以直接在另一个非空数组找第k大的数字了
• 然后比较二者大小：
  • 较小者直接删除(假设是A[k/2]小，则删除A[0:k/2+1]的数字，即A[k/2]也删)
  • 较大者不变
•  删除后，这时直接将k更新为`k:=k-k/2`，然后再循环进行折半删除，开始循环 

code

class Solution(object):
    def get_median(self, nums1, nums2, k):
        while len(nums1) != 0 and len(nums2) != 0 and k > 1:
            tmp = k // 2
            if tmp > len(nums1) or tmp > len(nums2): # 若某个数组长度不够用了
                tmp = min(len(nums1), len(nums2))  # 则将数组的删除长度定为能删的最大长度
            if nums1[tmp-1] <= nums2[tmp-1]:  # 谁小削谁
                nums1 = nums1[tmp:]  # 其实应该是nums1[tmp-1+1:],指第tmp-1位置的后面部分保留，而要不取到第tmp-1位置，所以再+1
            else:
                nums2 = nums2[tmp:]
            k -= tmp
        if min(len(nums1),len(nums2)) == 0 :
            arr = nums2 if len(nums1) == 0 else nums1  # 非空的那个数组
            return arr[k-1]  # 选第k个位置的数字，对应index要-1
        else:  # 只有两种情况会跳出，所以不是数组为空，就是k=1.这个分类就是k=1
            return min(nums1[0], nums2[0])

    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total = len(nums1) + len(nums2)
        k = total // 2 
        if total % 2 == 1:  # 奇数
            return self.get_median(nums1, nums2, k+1)
        else:  # 偶数
            return (self.get_median(nums1,nums2, k) + self.get_median(nums1,nums2, k+1)) / 2