LeetCode - 4. Median of Two Sorted Arrays4. Median of Two Sorted Arrays Problem's Link

 ----------------------------------------------------------------------------

Mean: 

给定两个数组，求这两个数组的中位数.(要求时间复杂度为O(log(n+m))

analyse:

一开始用归并为一个数组的方法做了一下也AC了，看来lc的时间还是给的很宽的.

将本题转化为求第k大数就简单多了，其中求第k大数使用类似二分的方法来实现，从而将时间复杂度降到O(log(n+m)).

Time complexity: O(log(n+m)

view code

/**

* -----------------------------------------------------------------

* Copyright (c) 2016 crazyacking.All rights reserved.

*       Author: crazyacking

*       Date  : 2016-02-03-12.07

*/

#include <queue>

#include <cstdio>

#include <set>

#include <string>

#include <stack>

#include <cmath>

#include <climits>

#include <map>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

typedef long long(LL);

typedef unsigned long long(ULL);

const double eps(1e-8);

/*Solution 1*/

class Solution

{

   //求A和B数组的第k大数

   int getMedian(int A[], int m, int B[], int n,int k)

   {

       if(m>n)

           return getMedian(B,n,A,m,k); //默认A为短数组

       if(m==0)

           return B[k-1];

       if(k==1)

           return min(A[0], B[0]);

       int pa = min(k/2, m);

       int pb = k - pa;

       if(A[pa-1] < B[pb-1])

       {

           return getMedian(A+pa, m-pa, B, n, k-pa);

       }

       else if(A[pa-1] > B[pb-1])

           return getMedian(A, m, B+pb, n-pb, k-pb);

       else

           return A[pa-1];

       return 0;

   }

public:

   double work(int A[], int m, int B[], int n)

       if((m+n)%2 == 0)

           return (getMedian(A, m,B, n, (m+n)/2) + getMedian(A, m,B, n, (m+n)/2+1)) /2.;

           return getMedian(A, m,B, n, (m+n)/2+1);

   double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)

       int A[10000],B[10000];

       int idx=0;

       for(auto p:nums1)

           A[idx++]=p;

       idx=0;

       for(auto p:nums2)

           B[idx++]=p;

       int m=nums1.size();

       int n=nums2.size();

       double ret=work(A,m,B,n);

       return ret;

};

/*Solution 2*/

/*

       auto it1=nums1.begin();

       auto it2=nums2.begin();

       vector<int> a;

       while(it1!=nums1.end() || it2!=nums2.end())

           if(it1==nums1.end() && it2!=nums2.end())

           {

               a.push_back((*it2));

               it2++;

           }

           else if(it1!=nums1.end() && it2==nums2.end())

               a.push_back(*it1);

               it1++;

           else if(it1!=nums1.end() && it2!=nums2.end())

               if((*it1)<(*it2))

               {

                   a.push_back(*it1);

                   it1++;

               }

               else

                   a.push_back(*it2);

                   it2++;

       int len=a.size();

       double ans=(len%2)?(double)a[len/2]:(double)(a[len/2-1]+a[len/2])/2.;

       return ans;

int main()

     int n,m,temp;

     while(cin>>n>>m)

     {

         vector<int> a,b;

         for(int i=0;i<n;++i)

         {

             cin>>temp;

             a.push_back(temp);

         }

         for(int i=0;i<m;++i)

             b.push_back(temp);

         Solution solution;

         double ans=solution.findMedianSortedArrays(a,b);

         cout<<"===========ans==========="<<endl;

         cout<<ans<<endl;

     }

     return 0;

}