寻找两个有序数组的中位数算法(leetcode第4题)

题目描述：

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

算法：中位数定义

代码实现：

# include<stdlib.h>

int cmp_int(const void* e1, const void* e2)
{
	return *(int*)e1 - *(int*)e2;
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int newNums[2000]={0};
    for(int i=0;i<nums1Size;i++)
        newNums[i]=nums1[i];
    for(int i=0;i<nums2Size;i++)
        newNums[i+nums1Size]=nums2[i];
    int len=nums1Size+nums2Size;
    double ret=0;
    qsort(newNums,len,sizeof(newNums[0]),cmp_int);
    if(len%2==0) 
        ret=(double)(newNums[len/2]+newNums[len/2-1])/2.0;
    else 
        ret=(double)newNums[len/2];
    return ret;
}

算法：排序优化

代码实现：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int len=nums1Size+nums2Size;
    int arr[len];//创建足够大的新数组
    for(int i=0;i<nums1Size;i++) arr[i]=nums1[i];
    int m=nums1Size-1,n=nums2Size-1;
    int index=m+n+1;
    while(n>=0){//排序(从小到大)
        while(m>=0 && nums1[m]>nums2[n]){
            arr[index--]=nums1[m--];
        }
        arr[index--]=nums2[n--];
    }
    double ret;
    if(len%2==0) //偶数
        ret=(double)(arr[len/2]+arr[len/2-1])/2.0;
    else //奇数
        ret=(double)arr[len/2];
    return ret;

}

算法：二分法

代码实现：

double findTheKthNumber(int *nums1,int nums1Size,int *nums2,int nums2Size,int k){
    // int i=0,j=0;
    // int delta=k/2-1;
    // while(1){
    //     if(i>=nums1Size){
    //         return nums2[k-nums1Size-1];
    //     }
    //     if(j>=nums2Size){
    //         return nums1[k-nums2Size-1];
    //     }
    //     if(nums1[i+delta]>nums2[j+delta]){
    //         if(k==1) return (double)nums1[i+delta];
    //         j+=delta+1;
    //     }
    //     else{
    //         if(k==1) return (double)nums2[j+delta];
    //         i+=delta+1;
    //     }
    //     k-=k/2;
    //     delta=k/2-1;
    // }
        int m = nums1Size;
        int n = nums2Size;
        int index1 = 0, index2 = 0;

        //二分查找
        while (1) {
            // 边界情况
            if (index1 == m) {
                return nums2[index2 + k - 1];
            }
            if (index2 == n) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return nums1[index1]>nums2[index2]?nums2[index2]:nums1[index1];
            }

            // 正常情况
            int newIndex1 = index1+k/2-1>m-1?m-1:index1+k/2-1;
            int newIndex2 = index2+k/2-1>n-1?n-1:index2+k/2-1;
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
}

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    //A: 1 3 4 9
    //B: 1 2 3 4 5 6 7 8 9
    //ret-->4
    int len=nums1Size+nums2Size;
    if(len%2==0){//偶数
        return (findTheKthNumber(nums1,nums1Size,nums2,nums2Size,len/2)+
findTheKthNumber(nums1,nums1Size,nums2,nums2Size,len/2+1))/2.0;
    }
    else{//奇数
        return findTheKthNumber(nums1,nums1Size,nums2,nums2Size,len/2+1);
    }

}