LeetCode题解

第4题，寻找两个有序数组的中位数

给定两个大小为 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

原题如上，解法如下：

python版

class Solution(object):
    def getk(self,nums1,start1,nums2,start2,n):
        if start1 >= len(nums1):
            return nums2[start2 + n - 1]
        if start2 >= len(nums2):
            return nums1[start1 + n - 1]
        if n == 1:
            return min(nums1[start1],nums2[start2])
        half = min(int(n/2),min(len(nums1)-start1,len(nums2)-start2))
        if nums1[start1 + half - 1] < nums2[start2 + half - 1]:
            return self.getk(nums1, start1 + half, nums2, start2, n - half)
        else:
            return self.getk(nums1, start1 , nums2, start2 + half, n - half)
        
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        left = int((len(nums1)+len(nums2)+1)/2)
        right = int((len(nums1)+len(nums2)+2)/2)
        return (self.getk(nums1,0,nums2,0,left) + self.getk(nums1,0,nums2,0,right))*0.5

c语言版

int min(int a, int b){
    if(a > b){
        return b;
    }else{
        return a;
    }
}

int getk(int* nums1, int nums1Size, int start1, int* nums2, int nums2Size, int start2, int n){
    if(start1 >= nums1Size)
        return nums2[start2 + n - 1];
    if(start2 >= nums2Size)
        return nums1[start1 + n - 1];
    if(n == 1)
        return min(nums1[start1], nums2[start2]);
    int half = min(n/2,min(nums1Size - start1, nums2Size - start2));
    if(nums1[start1 + half - 1] < nums2[start2 + half - 1]){
        return getk(nums1, nums1Size, start1 + half, nums2, nums2Size, start2, n - half);
    }else{
        return getk(nums1, nums1Size, start1, nums2, nums2Size, start2 + half, n - half);
    }
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int left = (nums1Size + nums2Size + 1)/2;
    int right = (nums1Size + nums2Size + 2)/2;
    return (getk(nums1, nums1Size, 0, nums2, nums2Size, 0, left) + getk(nums1, nums1Size, 0, nums2, nums2Size, 0, right))/2.0;
}

解析

这道题目是一个LeetCode难度为困难的题目

但是单看题目会发现很简单，无非可以用到归并排序形成新数组，然后根据新数组长度的奇偶取中位数

但是题目要求的时间复杂度为log(m+n)，而归并排序的时间复杂度为(m+n)，所以这就是这个题目的难点

思路：

使用二分法和递归

首先，我们先解决以下(m+n)的奇偶数问题，即对奇数来说中位数就是数组的第(m+n+1)/2位，而对于偶数来说，中位数就是(m+n)/2位和((m+n)/2)+1位的加和平均。其实可以将奇偶数放在一起考虑，即可以算出int((m+n+1)/2)和int((m+n+2)/2)的加和平均。对奇数和偶数来说都可以适用。

所以只要找到在两个有序数组排序组合后的第int((m+n+1)/2)个值和第int((m+n+2)/2)值就可以。

所以问题就划归为在两个有序数组中找第k值问题。

如果我们一个一个取比较，即归并排序后再去找k值，那么时间复杂度(m+n)，为了使时间复杂度为log(m+n)我们要用到二分法和递归：即我们可以一半一半的排除寻找。

构造getk函数：

已知nums1和nums2 ，设nums = nums1 $ nums2

符号$的定义是sorted(nums1+nums2)

示意图：

nums1 = [1, 3, 6, 7]

nums2 = [2, 4, 5, 8]

k = 7 k/2 = 3(向下取整) start1 = 0 start2 = 0

如图 nums1[3 - 1] > nums2[3 - 1]，则就可以推断2，4，5都小于nums[7-1]，即都可以舍去

k = 7 - 3 = 4 k/2 = 2 start1 = 0 start2 = 3

如图 nums1[2 - 1] < nums2[3 + 2 - 1]，则可以判断1，3都小于nums[7-1]，即都可以舍去

k = 4 - 2 k/2 = 1 start1 = 2 start2 = 3

如图 nums1[2 + 1 -1] < nums2[3 + 1 -1]，则可以判断6小于nums[7 - 1]，即可以舍去。

k = 2 -1 start1 = 3 start2 = 3

此时k = 1 即就是在两个数组中没有舍弃的数字中找到最小的数字，比较nums1[3 - 1]和nums2[3 - 1]取最小值就是我们开始要取的getk了

以上就是对一般情况下的求取，现在讨论特殊情况：

nums1 || nums2 == none
len(nums1) < k/2 or len(nums2) < k/2
在递归时 k/2 > len(nums1) - start1 or k/2 > len(nums2) - start2

其实上述可以用一种特殊情况总结，即

start1 >= len(nums1) or start2 >= len(nums2)

此时则return nums2[start2 + k -1]

这种特殊情况总伴随者下述：

即剩下的数字不足以二分法，则此时选取最小能舍去的步数，则每次判断可舍去的步数可用如下来求取：

half = min(int(n/2),min(len(nums1)-start1,len(nums2)-start2))

使用递归来求取k位值，每次可以舍去half个值，则剩下问题就是求取剩下数组们的k-half位值，知道问题缩小到求取的值为1位，则此时就返回return min(nums1[start1-1],nums2[start2-1])

其中start1和start2是变化的，即如果在上次舍去nums1数组half个值时，start1 = start1 +half，start2同理