题目：

 

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)).Subscribe to see which companies asked this question

解题思路：

　　我自己想的方法，先排序在查找。两个数组，首先想到是归并排序，然后再查找两个数组合并之后的中间元素即为中位数。我们分析下时间复杂度主要用在了归并排序上，为O((m+n)log(m+n))，显然不符合题目要求。题目要求是O(log(m+n))，但是我将这个方法的代码提交上去，仍然通过了，说明LeetCode的编译平台并没有严格按照ACM OJ这种要求来设置。排序后查找的代码如下所示：

1 //方法一：归并排序后查找：O((m+n)lg(m+n))，奇怪竟然通过了 2 double findMedianSortedArrays(vector
     
      & nums1, vector
      
       & nums2) 3 { 4     size_t n1 = nums1.size(), n2 = nums2.size(); 5     size_t n = n1+n2; 6     vector
       
         nums(n,0); 7  8     assert(n > 0); 9     10     nums1.push_back(INT_MAX);11     nums2.push_back(INT_MAX);12 13     size_t i = 0, j = 0, k = 0;14     while(i < n1 || j < n2) {15         if (nums1[i] <= nums2[j]) {16             nums[k++] = nums1[i++];17         }18         else19             nums[k++] = nums2[j++];20     }21 22     return ((n%2) ? (double)nums[(n-1)/2]:(double)(nums[(n-1)/2]+nums[n/2])/2);23 }
       
      
     

　　

　　看了下本题的难度系数，属于Hard级别的，说明本题不是那么容易对付的，又看了一下本题的Tag，其中罗列了两个重要的Tag：Divide and Conquer和Binary Search，说明本题需要用到两个方法：分治法和二分查找法，看了讨论里面，发现一种方法是这样的：求有序数组A和B有序合并之后第k小的数！如果A[k/2-1]<B[k/2-1]，那么A[0]~A[k/2-1]一定在第k小的数的序列当中，可以用反证法证明。详细的思路请见。代码如下：

1 //方法二：二分法：O(lg(m+n)),满足题目要求 2 //get the kth number of two sorted array 3 double findkth(vector
     
      ::iterator a,int m, 4                vector
      
       ::iterator b,int n, 5                int k) 6 { 7     if(m >  n) 8         return findkth(b,n,a,m,k); 9     if(m == 0)10         return b[k-1];11     if(k == 1)12         return min(*a,*b);13 14     int pa = min(k/2,m),pb = k - pa;15     if(*(a + pa - 1) < *(b + pb -1))16         return findkth(a+pa,m-pa,b,n,k-pa);17     else if(*(a + pa -1) > *(b + pb -1))18         return findkth(a,m,b+pb,n-pb,k-pb);19     else20         return *(a+pa-1);21 }22 23 double findMedianSortedArrays1(vector
       
        & nums1, vector
        
         & nums2) {24     vector
         
          ::iterator a = nums1.begin();25     vector
          
           ::iterator b = nums2.begin();26 int total = nums1.size() + nums2.size();27 28 // judge the total num of two arrays is odd or even29 if(total & 0x1)30 return findkth(a,nums1.size(),b,nums2.size(),total/2+1);31 else32 return (findkth(a,nums1.size(),b,nums2.size(),total/2) + findkth(a,nums1.size(),b,nums2.size(),total/2 + 1))/2;33 }