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

题意

给定两有序数组，是否为空未知，升序降续未知。合并两数组并排序，返回新数组的中位数 要求时间复杂度为O(log (m+n))

思路

其实就是合并数组找k大数，只是题目给定数组的可能性比较多，所以细节上会有些麻烦，具体见代码注释

我的复杂度是O(m+n)，与题目要求差不止一档，但还是ac了。

想了想要是按题目要求的复杂度，应该是类似求逆序对数的跳跃式计数，具体细节想想就头大，等个黄道吉日再好好尝试下

代码

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) 
{
    int rel1=0,rel2=0,f1,f2,i=0,num,start1,end1,start2,end2;
    num=(nums1Size+nums2Size)/2;//因为数组总长度可能偶数位，所以创两个rel来保存结果
    if(nums1[0]<=nums1[nums1Size-1])
    {
        start1=0;//起点
        end1=nums1Size-1;//终点
        f1=1;//标记升序或逆序
    }
    else
    {
        end1=0;
        start1=nums1Size-1;
        f1=0;
    }
    if(nums2[0]<=nums2[nums2Size-1])
    {
        start2=0;
        end2=nums2Size-1;
        f2=1;
    }
    else
    {
        end2=0;
        start2=nums2Size-1;
        f2=0;
    }
    while(i<=num)//找num次
    {
        if(start1>end1&&f1==1 || start1<end1&&f1==0)//判断nums1是否已遍历完，同时，数组为空的情况也会在次处理
        {
            rel1=rel2;
            rel2=nums2[start2];
            if(f2)
            {
                start2++;//升序+
            }
            else
            {
                start2--;//逆序-
            }
        }
        else if(start2>end2&&f2==1 || start2<end2&&f2==0)
        {
            rel1=rel2;
            rel2=nums1[start1];
            if(f1)
            {
                start1++;
            }
            else
            {
                start1--;
            }   
        }
        else if(nums1[start1]<=nums2[start2])//若两数组都未遍历完则比较大小
        {
            rel1=rel2;
            rel2=nums1[start1];
            if(f1)
            {
                start1++;
            }
            else
            {
                start1--;
            }       
        }
        else
        {
            rel1=rel2;
            rel2=nums2[start2];
            if(f2)
            {
                start2++;
            }
            else
            {
                start2--;
            }
        }
        i++;
    }
    return (nums1Size+nums2Size)%2==0 ? (double)((rel1+rel2)*1.0/2.0) : rel2;
}