题目

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

解答

就是寻找两个数组的中位数。如果将两个数组进行快排，可能有点慢。下面的代码花费72ms.

void quicksort(int r[],int s,int e) 
{ 
   int t = r[s];//哨兵，为开头的那个 
   int f = s+1; 
   int b = e;//f为前向指针，从s+1开始，b为反向指针，从e开始 
   int m = 0; 
   if(s>=e)return;//退出条件 
    
   while(f<=b) 
   { 
       while(f<=b&&r[f]<=t) f++;//在前面找比哨兵大的元素 
       while(f<=b&&r[b]>=t) b--;//在后面找比哨兵小的元素 
       //交换这两个元素 
       if(f<b){ 
            m = r[f]; 
            r[f] = r[b]; 
            r[b] = m; 
            f++;    b--; 
       } 
   } 
   //交换哨兵和r[b],r[b]肯定要比哨兵小 
   r[s] = r[b]; 
   r[b] = t; 
   //排两边的 
   quicksort(r,s,b-1); 
   quicksort(r,b+1,e); 
} 
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int allnum=nums1Size+nums2Size;
    int num[allnum],i=0,s1=0,s2=0;
    double ans=0;
    for(s1=0;s1<nums1Size;s1++)
    num[s1]=nums1[s1];
    for(s2=0;s2<nums2Size;s2++)
    num[nums1Size+s2]=nums2[s2];
    
    quicksort(num,0,allnum-1);
  
    if(allnum%2==1)
        ans=(double)num[(allnum-1)/2];
    else
        ans=((double)num[allnum/2]+(double)num[allnum/2-1])/2;
    return ans;
}

我们已知两个数组都是已经排好序的，因此可以挨个遍历两个数组，直至找到中间的那个数为止。这样花费了56ms.

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {
    int allnum=nums1Size+nums2Size;
    int num[allnum],i=0,s1=0,s2=0;
    double ans=0;
    for(i=0;i<allnum/2+1;i++)
    {
        if(s1<nums1Size&&s2<nums2Size)
        {
            if(nums1[s1]<nums2[s2])
            {
                num[i]=nums1[s1];s1++;
            }
            else
            {
                num[i]=nums2[s2];s2++;
            }
        }
        else if(s1==nums1Size)
        {
            num[i]=nums2[s2];s2++;
        }
        else
        {
            num[i]=nums1[s1];s1++;
        }
    }
    if(allnum%2==1)
        ans=(double)num[(allnum-1)/2];//需要转为double类型
    else
        ans=((double)num[allnum/2]+(double)num[allnum/2-1])/2;

    return ans;
}