leetcode_4

发表于   |   分类于

Median of Two Sorted Arrays

题目戳这

题意

给你两个已经从小到大排好序的数组，如果将这两个数组有序的合并，求中位数，并且要求算法复杂度为log(m+n)

解法

这道题目如果不要求复杂度的话就很简单，直接两个数组合并排序然后求中位数，但是那样的算法那复杂度为(m+n)log(m+n)。

这题其实可以套用求第k大元素的方法，对于两个有序数组A，B 我们假设C=A+B，如果A[k/2-1]<B[k/2-1]，k/2-1就是各数组中的第k/2大的元素，通过上面的比较我们可以看出，A[0]到A[k/2-1]区间内的值是不可能为C的第K大的值。

上面的结论我们可以用反证法来证明。假设A[k/2-1]大于第K大的值，那么我们认为是第k+1那么大，则在A数组中，小于A[k/2-1]的值至多有k/2-1个，在B数组中比它小的也至多有k/2-1个(因为A[k/2-1]<B[k/2-1])，则至多有k-2那么多元素是小于A[k/2-1]，这与A[k/2-1]为第k+1大的值是矛盾的，故假设不成立。

通过上面的证明我们就可以知道，当A[k/2-1]<B[k/2-1]时，我们就可以把A[0]-A[k/2-1]这些数抛弃掉，因为它们不可能是第k大的值.

反之亦然。

这就是一个递归的过程了，我们注意这么几个递归边界:

  1. 如果某个数组的长度在递归中为0了(比如是a)，那我们就输出b[k-1]，因为这是b[k-1]就是第k大的数据。
  2. 当k为1的时候，我们只要比较a,b两个数组的首个元素a[0],b[0]哪个更小就行，它们中的一个就是第K大的数据。
  3. 当A[k/2-1] == B[k/2-1]时，它们就都是第K大的值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution(object):
    def findkthElement(self, arr1, m, arr2, n, k):
        if m > n: # 保证arr1是规模比较小的数组
            return self.findkthElement(arr2, n, arr1, m, k)
        if m == 0: # 递归边界1
            return arr2[k-1]
        if k == 1: # 递归边界2
            return arr1[0] if arr1[0]<arr2[0] else arr2[0]
        
        pa = k//2 if k//2 < m else m # 保证k/2是小于m的
        pb = k - pa  # k/2或者k-m
        if arr1[pa-1] < arr2[pb-1]: # arr1[k/2-1] < arr2[k/2-1]
            return self.findkthElement(arr1[pa:], m-pa, arr2, n, k-pa)
        elif arr1[pa-1] > arr2[pb-1]:
            return self.findkthElement(arr1, m, arr2[pb:], n-pb, k-pb)
        else:
            return arr1[pa-1] # arr1[k/2-1] = arr2[k/2-1]
        pass
    
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        total = len(nums1)+len(nums2)
        m = len(nums1)
        n = len(nums2)
        if total % 2 == 1: # 奇数的情况
            return self.findkthElement(nums1, m, nums2, n, total//2+1)
        else:    # 偶数的情况
            return (self.findkthElement(nums1, m, nums2, n, total//2) + self.findkthElement(nums1, m,
            nums2, n, total//2+1))*1.0/2