【leetcode】Median of Two Sorted Arrays

Median of Two Sorted Arrays

There are two sorted arrays A and B 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)).

最简单的，把两个数组组合到一起，然后排序，找到中位数，不过不符合复杂度要求

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(int A[], int m, int B[], int n) {
 4        
 5         int i,j;
 6         vector<int> arr(m+n);
 7        
 8         for(i=0;i<m;i++)
 9             arr[i]=A[i];
10        
11         for(j=0;j<n;j++)
12             arr[m+j]=B[j];
13        
14         sort(arr.begin(),arr.end());
15        
16         if((m+n)%2==0)
17             return (arr[(m+n)/2]+arr[(m+n)/2-1])/2.0;
18         else
19             return arr[(m+n)/2];
20     }
21 };

解法二，不进行排序，直接在合并数组时确定顺序，不符合复杂度要求：

 1 class Solution {
 2 public:
 3     double findMedianSortedArrays(int A[], int m, int B[], int n) {
 4        
 5         int i,j,k;
 6         i=j=k=0;
 7        
 8         vector<int> arr(m+n);
 9         while(i<m||j<n)
10         {
11             int tmp;
12             if(i>=m)
13             {
14                 tmp=B[j];
15                 j++;
16             }
17             else if(j>=n)
18             {
19                 tmp=A[i];
20                 i++;
21             }
22             else if(A[i]<B[j])
23             {
24                 tmp=A[i];
25                 i++;
26             }
27             else
28             {
29                 tmp=B[j];
30                 j++;
31             }
32             arr[k]=tmp;
33             k++;
34         }
35        
36         if((m+n)%2==0)
37             return (arr[(m+n)/2]+arr[(m+n)/2-1])/2.0;
38         else
39             return arr[(m+n)/2];
40     }
41 };

解法三，通过在两个排列好的数列中寻找第K小的元素来寻找中位数

第1小，代表了最小的数

首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。如果A[k/2-1]<B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素中。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。

当A[k/2-1]>B[k/2-1]时存在类似的结论。

当A[k/2-1]=B[k/2-1]时，我们已经找到了第k小的数，也即这个相等的元素

 1 class Solution {
 2 public:
 3  
 4  int findKth(int A[],int m,int B[],int n,int k)
 5     {
 6           //为了后续计算方便，使得B的长度始终大于B的长度
 7         if(m>n)
 8         {
 9             return findKth(B,n,A,m,k);
10         }
11        
12         //如果第一个数组为空了，则返回第k小的数
13         if(m==0)
14         {
15             return B[k-1];
16         }
17        
18         //如果寻找第一小的数
19         if(k==1)
20         {
21             return min(A[0],B[0]);
22         }
23        
24         //第k/2个元素，或者是最后一个元素
25         int pa=min(m-1,k/2-1);
26         //保证A,B共取了k个元素
27         int pb=(k-(pa+1))-1;
28        
29         
30         if(A[pa]<B[pb])
31         {
32             //当排除了pa+1个元素后，则我们下一次寻找的就是k-(pa+1)大的元素了
33             return findKth(A+(pa+1),m-(pa+1),B,n,k-(pa+1));
34         }
35         else if(A[pa]>B[pb])
36         {
37             return findKth(A,m,B+(pb+1),n-(pb+1),k-(pb+1));
38         }
39         else if(A[pa]==B[pb])
40         {
41             return A[pa];
42         }
43     }
44  
45     double findMedianSortedArrays(int A[], int m, int B[], int n) {
46        
47         if((m+n)%2==0)
48             return (findKth(A,m,B,n,(m+n)/2)+findKth(A,m,B,n,(m+n)/2+1))/2.0;
49         else
50             return findKth(A,m,B,n,(m+n)/2+1);
51     }
52 };