【LeetCode】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)).
有两个排序的数组A和B分别是m和n。找到两个排序数组的中值。总的运行时间复杂度应该是O（log（m+n））。

思路一：

//合并数组，然后快速确定中间值

• （1）第一步将两个有序数组合并成一个有序的数组（或者向量）（类似于两个有序链表的合并）
• （2）得到最终的数组（或者向量）长度为m+n，然后判断是有奇数个值，还是有偶数个值
• （3）如果有奇数个值，那么只有一个中间值，对应的编号为 （数组（或者向量）长度 -1）/2，取出值，直接返回
• （4）如果有偶数个值，那么有两个中间值，对应编号为：
  1）数组（或者向量）长度 /2
  2）数组（或者向量）长度 /2 - 1
• （5）取出对应的值，然后求平均，得到最终结果 */

参考代码

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int C[m+n];
        memset(C,0,(m+n)*sizeof(int));
        int k=0;
        int i=0,j=0;//定义下标，其中i是向量1的下标，j是向量2的下标
        while(i<m&&j<n)
        {

            if(A[i]<=B[j])
                C[k++]=A[i++];
            else
                C[k++]=B[j++];

        }
         //数组B还有剩余部分，将数组B剩余部分依次插入
        if(i==m)
        {
            while(j<n)
                C[k++]=B[j++];
        }   
        else if(j==n)//数组A还有剩余部分，将数组A剩余部分依次插入
        {
            while(i<m)
                C[k++]=A[i++];
        }
        if((m+n)&1)//有奇数个值（一个中间值）
            return C[(m+n)>>1]*1.0;
        else////有偶数个值（两个中间值，求平均值）
            return (C[(m+n)>>1]+C[((m+n)>>1)-1])*0.5;   ////-号优先级比>>高
    }
};

思路二：（最优解）

• 这道题更通用的形式，就是找到两者所有元素中的第k小的元素。
• O(m+n)的解法比较直观，直接merge两个数组，然后求第k大值。
• 不过我们仅仅需要的是找第k大值，是不需要“排序”这莫昂贵的操作的。可以用一个计数器，记录当前已经找到第m大的元素了，同时使用两个指针pa，pb，分别指向A、B两个数组的第一个元素，类似于merge sort（归并排序）的原理，如果A当前元素小则pa++；同时m++；如果B当前元素小，那么pb++；同时m++；最终当m==k，就得到答案了，O（k）的空间，O（1）的空间，但是当k接近m+n时，时间还是O（m+n）的。
• 还没有更好思路呢？我们换种思路，我们可以从k入手，如果每次都能删除一个一定在第k大元素之前的元素呢，此时，，我们需要进行k次，如果每次删一半呢？由于A、B都是有序，我们可以类似于二分查找，也利用了有序。
• 假设两个数组个数都是大于k/2，我们将A的第k/2(即A[k/2-1])和B的第k/2个元素（即B[k/2-1]）进行比较，有如下三种情况(为了此处方便设k为偶数，即共奇数个数，所得结论通用的）：
  

• A[K/2-1] == B[K/2-1]
  
• A[K/2-1] > B[K/2-1]
  
• A[K/2-1] < B[K/2-1]
• 如果第二种情况，就意味着A[K/2-1]不可能大于AUB的第k大元素。
• 因此，可以删除A组中k/2数据了，同理，可以删除B组中k/2数据。
  当A[k/2-1]=B[k/2-1]时，说明找到了第k大的元素，直接返回A[k/2-1]或B[k/2-1]即可。
  因此，我们可以写一个递归函数。那么函数什么时候终止呢？
  （1）当A或B是空时，直接返回A[k-1]或B[k-1]
  （2）当k=1时，返回min(A[0],B[0])
  （3）当A[k/2-1] == B[k/2-1]时，返回A[k/2-1]或B[k/2-1]

参考代码

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int total = m+n;
        if(total & 1)
            return findkth(A,m,B,n,total/2+1);
        else
            return (findkth(A,m,B,n,total/2)+findkth(A,m,B,n,total/2+1))/2;
    }

    double findkth(int A[], int m, int B[], int n, int k)
    {
        if(m>n)
            return findkth(B,n,A,m,k);
        if(m==0)
            return B[k-1];
        if(k==1)
            return min(A[0],B[0]);
        int midA = min(k/2,m);
        int midB = k-midA;
        if(A[midA-1]<B[midB-1])
        {
            return findkth(A+midA,m-midA,B,n,k-midA);
        }
        else if(A[midA-1]>B[midB-1])
        {
            return findkth(A,m,B+midB,n-midB,k-midB);
        }
        else//A[midA-1]==B[midB-1]
            return A[midA-1];
    }
};

结语

夜的寂静，只为迎接绚丽的日出