4.md

#4. Median of Two Sorted Arrays 题目链接

/*
 * 利用归并的方法进行查找，找到后返回
 * 但是时间复杂度是O(m + n)，不是O(lg(m + n)
 * todo 改进时间复杂度
 */
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int sumSize = nums1Size + nums2Size;
    int flag = sumSize % 2;
    int mid = sumSize / 2;
    int *newNums = (int *)malloc(sizeof(int) * sumSize);
    int i,j,k;
    for (i = j= k = 0; j < nums1Size && k < nums2Size; i++)
    {
        if (nums1[j] < nums2[k])
        {
            newNums[i] = nums1[j++];
        } else
        {
            newNums[i] = nums2[k++];
        }
        if (i == mid && !flag)
            return ((double)newNums[i] + newNums[i-1])/2;
        else if (i == mid)
            return (double)newNums[i];
    }
    if (j == nums1Size)
    {
        for (k; k < nums2Size; k++, i++)
        {
            newNums[i] = nums2[k];
            if (i == mid && !flag)
                return ((double)newNums[i] + newNums[i-1])/2;
            else if (i == mid)
                return (double)newNums[i];
        }

    }
    else if (k == nums2Size)
    {
        for (j; j < nums1Size; j++, i++)
        {
            newNums[i] = nums1[j];
            if (i == mid && !flag)
                return ((double)newNums[i] + newNums[i-1])/2;
            else if (i == mid)
                return (double)newNums[i];
        }

    }
    return -1.0;
}