leetcode4-- Median of Two Sorted Arrays (两个有序数组中的第k小)(被面过)

leetcode4-- Median of Two Sorted Arrays (两个有序数组中的第k小)(被面过)

题目

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

这个题目要求的是两个已经排好序的数组,的中位数,即如果他们组成一个数组的话,其中位数,

其实这个题目可以general地问,即第k小,或者说第k大的元素。

当然最小最大的都比较容易做,其它情况的话,考虑二分法,用递归来做,

想法就是在其中一个数组中考虑一半,在另外一个数组中考虑一半,然后比较选出来的两个子数组的右端点的大小,然后决定下一次该从哪里开始找起,

如下

def findKth(self,lst1,lst2,k):  ## 这个k的意思是找到第k小的。
    if len(lst1)==0:
        return lst2[k-1]
    if len(lst2) ==0:
        return lst1[k-1]
    if k==1:
        return min(lst1[0], lst2[0])   ## 好返回二者中最小的一个.

    
    ## 这样弄是为了防止越界
    if len(lst1)<len(lst2):
        posa = min(k/2, len(lst1))   # 从短的那个取k/2个.
        posb = k-posa
    else:
        posb = min(k/2, len(lst2))
        posa = k - posb
        
    if lst1[posa-1] < lst2[posb-1]:   # 说明lst1的前posa个较小,因此第k小的只能从后面找
        return self.findKth(lst1[posa:], lst2, k-posa)
    elif lst1[posa-1]>lst2[posb-1]:
        return self.findKth(lst1,lst2[posb:], k-posb)
    else:
        return lst1[posa-1]
        

那么如果是返回中位数的话,就要看总共的长充是奇数还是even了。

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total = len(nums1)+len(nums2)
        if total%2==1:   ## 如果是奇数的话,找的就是中间的那个.
            return self.findKth(nums1,nums2,(total+1)/2)
        else:  ##如果是even的话就找选中间的两个的均值。
            return 1.0*(self.findKth(nums1,nums2, total/2)+self.findKth(nums1,nums2,total/2+1))/2
        

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦