寻找两个正序数组的中位数

寻找两个正序数组的中位数  

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

方法一
基本思路:归并排序，即将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先递归将它分成两个有序数组，然后将结果归并。
优点：实现简单，逻辑简单，类似对一个更大的数组重新排序
缺点：需要一个额外的空间，空间复杂度高

int main()
{
    int nums1[] = {1,2,4,9};
    int nums2[] = {1,2,3,4,5,6,7,8,9,10};
    int nums1Size = 4, nums2Size = 10;　　　　　　//测试数组

    float mid = 0;
    int left = 0, right = nums1Size;　　　　　　//左右两个有序数组
    int len = nums1Size + nums2Size;　　　　　　
    int *aux = malloc(sizeof(int) * len);　　//辅助数组，用于存储两个有序数组
    int *result = malloc(sizeof(int) * len); //保存归并结果

    for(int i = 0; i < nums1Size; i++)　　　　//装入辅助数组
    {
        aux[i] = nums1[i];
    }

    for(int j = nums1Size , m = 0; j < len; j++, m++)
    {
        aux[j] = nums2[m];
    }

　　/*
　　进行归并
　　进行4个判断条件
　　左半边数组耗尽
　　右半边数组耗尽
　　右半边的当前数组小于左半边数组元素
　　右半边的当前数组元素大于或等于左半边数组元素
　　　　　　　　　　　　　　*/
    for(int k = 0; k < len; k++)　　　　　
    {
        if(left > nums1Size - 1)
            result[k] = aux[right++];
        else if(right > len)
            result[k] = aux[left++];
        else if(aux[right] < aux[left])
            result[k] = aux[right++];
        else
            result[k] = aux[left++];

    }

    mid = len%2 == 0 ? (result[len/2] + result[len/2 - 1])/2.0 : result[len/2];return 0;
}

 程序可以正常在Code::Block上运行，但无法通过leetcode编译（不懂）

方法二

基本思路：二分查找

根据中位数的定义，对于两个有序数组，若m+n为奇数， 中位数是第（m+n）/2个数；若m+n为偶数，中位数为第（m+n）/2 与第（m+n）/2 -1个数的平均值

因此，这道题可以转化成寻找两个有序数组中的第 k 小的数

其实在两个有序数组中，寻找中位数并不需要每一个元素都遍历到。

根据有序数组的性质，可以假设中位数为第k小的数，那么对于比第k/2小的数，其实就可以直接排除了

更一般的情况 A[1] ，A[2] ，A[3]，A[k/2] ... ，B[1]，B[2]，B[3]，B[k/2] ... ，如果 A[k/2]<B[k/2] ，那么A[1]，A[2]，A[3]，A[k/2]都不可能是第 k 小的数字。

A 数组中比 A[k/2] 小的数有 k/2-1 个，B 数组中，B[k/2] 比 B[k/2] 小的数同样有k/2-1，假设 B[k/2] 前边的数字都比 A[k/2] 小，也只有 k/2-1 个，所以比 A[k/2] 小的数字最多有 k/1-1+k/2-1=k-2个，所以 A[k/2] 最多是第 k-1 小的数。而比 A[k/2] 小的数更不可能是第 k 小的数了，所以可以把它们排除。

因此，可以归纳出以下几点

• 若A[k/2-1]<B[k/2-1], 则A[0]~A[k/2-1]的元素都可以排除
• 若A[k/2-1]>B[k/2-1]，则B[0]~B[k/2-1]的元素都可以排除
• 若相等，当做第一种情况处理
• 若k/2>len_A(数组A的长度)，毫无疑问，第k小的数，只能在数组B中

采用递归实现

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int len1 = nums1Size ,len2 = nums2Size;
    int left = (len1 + len2 + 1)/2;
    int right = (len1 + len2 + 2)/2;
　　//若为奇数，重复计算2遍；若为偶数，直接出结果
    return (getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, left) + getKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, right))*0.5;

}

int getKth(int *nums1, int start1, int end1, int *nums2, int start2, int end2, int k)
{
    int len1 = end1 - start1 + 1;
    int len2 = end2 - start2 + 1;

    if(len1 > len2)　　　　　　　　　　//确保len1的长度总为最短的，方便计算
        getKth(nums2, 0, len2 - 2, nums1, 0, len1 - 1,  k);
    if(len1 == 0)　　　　　　　　　　　　//特殊情况的处理
        return nums2[start2 + k - 1];
    if(k == 1)
        return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2];

    int min1 = (len1 < k/2) ? len1 : k/2;
    int min2 = (len2 < k/2) ? len2 : k/2;

    int i = start1 + min1 - 1;　　　　　　//可以当成指针一样理解，操控指针移动
    int j = start2 + min2 - 1;
    if(nums1[i] > nums2[j])　　　　　　//排除一次，更新第k小的数
    {
        return getKth(nums1 , start1, end1, nums2, j+1, end2, k - (j - start2 + 1));
    }
    else
    {
        return getKth(nums1, i+1, end1, nums2, start2, end2, k - (i - start1 + 1));
    }

            
}

程序可以正常在Code::Block上运行，但无法通过leetcode编译（不懂）

附：