两个排序数组的中位数

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

你可以假设 nums1 和 nums2 不同时为空。

示例1

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0

示例2

nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3)/2 = 2.5

代码实现

from math import floor
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        #1判断两个数组的length,进而知道中位数的大致位置
        #2调用findKth函数找到两个数组中的中位数位置上的数，就行求算
        
        l =len(nums1) + len(nums2)
        if l%2 ==1:
            return self.findKth(nums1, nums2, (l+1)/2)
        else:
            small = self.findKth(nums1, nums2, l / 2)
            big = self.findKth(nums1, nums2, l / 2 + 1 )
            return (small+big)/2.0
 
    def findKth(self, nums1, nums2, k):
        if len(nums1)==0:
            return nums2[k-1]
        if len(nums2)==0:
            return nums1[k-1]
        if k==1:
            return min(nums1[0],nums2[0])
        
        n1 = nums1[floor(k / 2) - 1] if len(nums1) >= k/2 else None
        n2 = nums2[floor(k / 2) - 1] if len(nums2) >= k/2 else None
        
        if n2 is None or (n1 is not None and n1<n2):
            return self.findKth(nums1[floor(k/2):], nums2, k-floor(k/2))
        return self.findKth(nums1, nums2[floor(k/2):], k-floor(k/2))

以上程序在自测用例的能通过，但是提交解答出了问题，TypeError: list indices must be integers or slices, not float 。原因应该是在if,else判断里的除法，当采用向下取整之后，运算结果为整数。

from math import floor
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        #1判断两个数组的length,进而知道中位数的大致位置
        #2调用findKth函数找到两个数组中的中位数位置上的数，就行求算
        
        l =len(nums1) + len(nums2)
        if l%2 ==1:
            return self.findKth(nums1, nums2, floor((l+1)/2))  #修改
        else:
            small = self.findKth(nums1, nums2, floor(l / 2))  #修改
            big = self.findKth(nums1, nums2, floor(l / 2) + 1 )  #修改
            return (small+big)/2.0


    def findKth(self, nums1, nums2, k):
        if len(nums1)==0:
            return nums2[k-1]
        if len(nums2)==0:
            return nums1[k-1]
        if k==1:
            return min(nums1[0],nums2[0])
        
        n1 = nums1[floor(k / 2) - 1] if len(nums1) >= k/2 else None
        n2 = nums2[floor(k / 2) - 1] if len(nums2) >= k/2 else None
        
        if n2 is None or (n1 is not None and n1<n2):
            return self.findKth(nums1[floor(k/2):], nums2, k-floor(k/2))
        else:
            return self.findKth(nums1, nums2[floor(k/2):], k-floor(k/2))

这个程序的重点是找到两个有序数组中第K小的数。

看到别人的解释是这样子的，http://chaoren.is-programmer.com/posts/42890.html

“求A和B数组中第k小的数的问题, 然后用k/2在A和B中分别找。比如k = 6, 分别看A和B中的第3个数, 已知 A1 < A2 < A3 < A4 < A5... 和 B1 < B2 < B3 < B4 < B5..., 如果A3 <＝ B3, 那么第6小的数肯定不会是A1, A2, A3, 因为最多有两个数小于A1, 三个数小于A2, 四个数小于A3。B3至少大于5个数, 所以第6小的数有可能是B1 (A1 < A2 < A3 < A4 < A5 < B1), 有可能是B2 (A1 < A2 < A3 < B1 < A4 < B2), 有可能是B3 (A1 < A2 < A3 < B1 < B2 < B3)。那就可以排除掉A1, A2, A3, 转成求A4, A5, ... B1, B2, B3, ...这些数中第3小的数的问题, k就被减半了。每次都假设A的元素个数少, pa = min(k/2, lenA)的结果可能导致k == 1或A空, 这两种情况都是终止条件”

如果还是不理解，就自己动手算一算，走一遍程序就懂了。一下是自己的划拉图，估计之后我也不能记得当初是怎么花的...