LeetCode 寻找两个有序数组的中位数

待我称王封你为后i 2023-07-10 08:14 5阅读 0赞

题目时间复杂度要求不高于O(log(m+n)),m，n分别是两个数组的长度。对数级的时间复杂度就应该用二分查找来做了。整体思路就是：先分别找到两个数组的中位数a，b，如果a<b，说明整体的中位数位于a的后半段或b的前半段；如果a>b，说明整体中位数位于a的前半段或b的后半段。不断这样二分下去即可。  
其实，这道题可以转换为寻找有序数组中的第k个数，对应于中位数的话，k=(m+n)/2。寻找过程如上。最后时间复杂度还可。官方给出的解答实在是让人头大，不通用，要是在面试情况下，基本上做不出来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]

class Solution:
        def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
            n1, n2 = len(nums1), len(nums2)
            #处理某个数组为空数组的情况
            if n1 == 0:
                if n2&1 == 1:  #数组长度为奇数
                    return nums2[n2//2]
                return (nums2[n2//2] + nums2[n2//2-1]) / 2
            if n2 == 0:
                if n1&1 == 1:
                    return nums1[n1//2]
                return (nums1[n1//2] + nums1[n1//2-1]) / 2
            L = n1 + n2
            if L&1 == 1:   #总数为奇数时，寻找的第k个数就是L//2+1
                return self.find_kth(nums1, 0, nums2, 0, n1, n2, L//2+1)
            #总数为偶数的情况
            return (self.find_kth(nums1, 0, nums2, 0, n1, n2, L//2) + self.find_kth(nums1, 0, nums2, 0, n1, n2, L//2+1)) / 2
    
        def find_kth(self, nums1, start1, nums2, start2, n1, n2, k):
            if start1 >= n1:   #起始索引大于等于数组长度，说明总体的第k个数，就是另外一个数组中的第k个数
                return nums2[start2+k-1]
            if start2 >= n2:
                return nums1[start1+k-1]
            if k == 1:  #k最小为1
                return min(nums1[start1], nums2[start2])
            mid1 = float('inf')
            mid2 = float('inf')
            if start1 + k//2 - 1 < n1:
                mid1 = nums1[start1+k//2-1]
            if start2 + k//2 - 1 < n2:
                mid2 = nums2[start2+k//2-1]
            #如果数组1的中位数小于数组2的，说明第k个数在数组1的前半段或数组2的后半段，
            #则数组1的初始索引要向后移k/2，数组2起始索引不变，同时减小k，因为整体寻找范围在缩小。
            #数组1中位数大于数组2中位数，同理。
            if mid1 < mid2:
                return self.find_kth(nums1, start1+k//2, nums2, start2, n1, n2, k-k//2)
            return self.find_kth(nums1, start1, nums2, start2+k//2, n1, n2, k-k//2)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301034454374.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2pheV93b25kZXI=,size_16,color_FFFFFF,t_70