array- Median of Two Sorted Arrays

题目描述：

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)).
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

题目解析：
1. 本题想在两个有序的数组中，找出两数组所有数的中位数。
2. array1的size为m,array2size为n.m+n为奇数，则需要求解合并数组中，第（m+n）/2+1大的数，若m+n为偶数，则需要求解合并数组中第（m+n）/2和（m+n）/2+1两数的平均数。
3. 有了时间复杂度O(log (m+n))的限制，所以常规的先合并在找第k大的数时间复杂度肯定会超，最快也是O(m+n)的复杂度。

---

// 由于array1和array2分别是有序数组，本体可以简化为寻找第k大的数。假设（m+n）/2 = k,则分别在array1和array2中寻找第k/2大和k-k/2大的数。
1. if(arr1[k/2] == arr2[k-k/2]),则直接返回arr1[k/2];
2. if(arr1[k/2] < arr2[k-k/2]),则可以删去arr1的前k/2个元素，在剩余元素中寻找第k-k/2大的数。
3. if(arr1[k/2] > arr2[k-k/2]), 做法与2一样。
// 此种方法，因为每次都会排除k/2个元素，所以时间复杂度，可以保证在O(log (m+n))级别。

代码：

    // 找寻第K小的数字  
    int FindKthDigit(int *nums1, int size1, int *nums2, int size2, int k)
    {
        // 始终保证arr1的size小于arr2的size
        if(size1>size2)
            return FindKthDigit(nums2, size2, nums1, size1, k);
        // 如果size1为0，只需直接在arr2中找出第k大的元素
        if(size1 == 0)
            return nums2[k-1];
        if(k==1)
            return nums1[0]<nums2[0] ? nums1[0] : nums2[0];
        // 防止溢出，则计算pos1时，取k/2和size1的小者作为pos1
        int pos1 = k/2 < size1 ? k/2 : size1;
        int pos2 = k-pos1;
        if(nums1[pos1-1] == nums2[pos2-1])
            return nums1[pos1-1];
        else if(nums1[pos1-1] < nums2[pos2-1])
            return FindKthDigit(nums1+pos1, size1-pos1, nums2, size2, k-pos1);
        else 
            return FindKthDigit(nums1, size1, nums2+pos2, size2-pos2, k-pos2);

    }


double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
        if(nums1Size==0 && nums2Size==0)
            return 0;

        if((nums1Size + nums2Size)%2)
            return FindKthDigit(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size)/2+1);
        else
        {
            return (FindKthDigit(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size)/2)+FindKthDigit(nums1, nums1Size, nums2, nums2Size, (nums1Size+nums2Size)/2+1))/2.0;
        }

}